Home Strings CamelCase matching

CamelCase matching

by nikoo28
1 comment

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

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

1 comment

You may also like

1 comment

E April 20, 2019 - 07:51

Cool
Thank you ????

Reply

Enclose codes in [code lang="JAVA"] [/code] tags

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

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More