Given a pattern and an input string, check if the input string matches the pattern.
Eg.
pattern: abab
input: howwhathowwhat
mapping: a => how, b => what
so match(abab, howwhathowwhat) -> true
match(abab, whathowhowwhat) -> false
match(“”, “”) -> true
match(“a”, “a”) -> true
match(“ab”, “abab”) -> true
match(“aaaa”, “howwhatwhathow”) -> false
match(“aaaa”, “whatwhatwhatwhat”) -> true
Each char in pattern string can match 1-n chars in input string. Same char can only match same string. Different chars can match same strings.
class Solution {
public boolean match(String pattern, String input) {
if (pattern == null || input == null || input.length() < pattern.length()) {
return false;
}
Map<Character, String> map = new HashMap<>();
return matchHelper(pattern, 0, input, 0, map);
}
public boolean matchHelper(String pattern, int index, String input, int inputIndex, Map<Character, String> map) {
if (index == pattern.length()) {
if (inputIndex == input.length()) {
return true;
}
return false;
}
char c = pattern.charAt(index);
if (map.containsKey(c)) {
String val = map.get(c);
if (inputIndex + val.length() <= input.length() && val.equals(input.substring(inputIndex, inputIndex + val.length()))) {
return matchHelper(pattern, index + 1, input, inputIndex + val.length(), map);
}
} else {
for (int i = inputIndex; i < input.length(); i++) {
String val = input.substring(inputIndex, i + 1);
map.put(c, val);
if (matchHelper(pattern, index + 1, input, i + 1, map)) {
return true;
}
map.remove(c);
}
}
return false;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.match("", "")); //true
System.out.println(s.match("a", "a")); //true
System.out.println(s.match("ab", "abab")); //true
System.out.println(s.match("abab", "howwhathowwhat")); //true
System.out.println(s.match("abab", "howwhatwhathow")); //false
System.out.println(s.match("aaaa", "howwhatwhathow")); //false
System.out.println(s.match("aaaa", "whatwhatwhatwhat")); //true
}
}
