LC291. Word Pattern II
Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.
Examples:
- pattern =
"abab", str ="redblueredblue"should return true. - pattern =
"aaaa", str ="asdasdasdasd"should return true. - pattern =
"aabb", str ="xyzabcxzyabc"should return false.
这题和World pattern I 的区别在于这里的str是没有分开的，所以就有很多种组合形式。利用全局Map存pattern对应的str， 如果匹配就递归匹配下一位，否则返回false。
public class Solution {
// pattern - str
Map<Character, String> map = new HashMap<>();
// set of str cuz hashmap.containsValue() cost O(n) time
Set<String> set = new HashSet<>();
public boolean wordPatternMatch(String pattern, String str) {
if(pattern.isEmpty()) return str.isEmpty();
if(map.containsKey(pattern.charAt(0))){
String val = map.get(pattern.charAt(0));
if(val.length() > str.length() || !str.substring(0, val.length()).equals(val)) return false;
if(wordPatternMatch(pattern.substring(1), str.substring(val.length()))) return true;
}else{
for(int i = 1; i <= str.length(); i++){
if(set.contains(str.substring(0, i))) continue;
// backtracking
map.put(pattern.charAt(0), str.substring(0, i));
set.add(str.substring(0, i));
if(wordPatternMatch(pattern.substring(1), str.substring(i))) return true;
map.remove(pattern.charAt(0));
set.remove(str.substring(0, i));
}
}
// not match at last
return false;
}
}
O(n^n), O(n)