CamelCase matching

Question: Given a set of queries and a pattern, we need to determine if some of those queries can be made from the given pattern by adding one or more lower case character. Output a boolean array where array[i] says true, if the query is possible, else false.

Input: queries= {“StudyAlgorithms”, “StudyAlgorithmsTest”, “StanAlluring”, “SimulationAlteration”, “StopStayAlive”}
pattern = “StAl”

Output: {true, false, true, true, false}

Let us try to understand the output.
The pattern defined to us is St*Al* (if we see it in terms of a regex)

• StudyAlgorithms can be made as St + “udy” + Al + “gorithms“
• StanAlluring can be made as St + “an” + Al + “luring“
• SimulationAlteration can be made as S + “imula” + t + “ion” + Al + “teration“

Other queries cannot be formed as either they do not follow the pattern or they add another upper case letter.

ALGORITHM

– Start for each string in the query array.
– For each string, match it with the pattern and pass the result.

The match process should be defined as:-

– Let ‘i’ be the query pointer.
– Let ‘j’ be the pattern pointer
– If char[i] == char[j], we need to advance both the pointers.
– If char[i] != char[j] and char[i] (query pointer) is a lower case letter, just advance the query pointer. We can keep going as we can add any number of lower case characters.
– If char[i] != char[j] and char[i] (query pointer) is a upper case letter, then return false. This means that we added a new uppercase letter and it would not match the pattern.

The code for the above algorithms can be written as:

public List<Boolean> camelMatch(String[] queries, String pattern) {
    List<Boolean> result = new ArrayList<>();

    char[] patternArr = pattern.toCharArray();

    // Start for each string in the query array
    for (String query : queries) {

        // Match it with the pattern
        boolean isMatch = match(query.toCharArray(), patternArr);

        // Pass the result
        res.add(isMatch);
    }

    return res;
}

private boolean match(char[] queryArr, char[] patternArr) {

    int j = 0; // pattern pointer

    // i is the query pointer
    for (int i = 0; i < queryArr.length; i++) {

        // If char[i] == char[j], we need to advance both the pointers.
        if (j < patternArr.length && queryArr[i] == patternArr[j]) { 
            j++; 
        } else if (queryArr[i] >= 'A' && queryArr[i] <= 'Z') {

            // If the query character is a uppercase letter, then return false.
            return false;
        }
    }

    // Just verify that pattern pointer reaches its length limit
    return j == patternArr.length;
}
Code language: Java (java)

A working solution can be found here. https://ideone.com/Vj89bz