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