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