# CamelCase matching

By | April 13, 2019

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
}

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;
}
```

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

Author: nikoo28

a tech-savvy guy and a design buff...

## One thought on “CamelCase matching”

This site uses Akismet to reduce spam. Learn how your comment data is processed.