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. Notes: You may assume both pattern and str contains only lowercase letters.
因为目标字符串可以任意划分,所以我们不得不尝试所有可能性。这里通过深度优先搜索的回溯法,对于pattern中每个字母,在str中尝试所有的划分方式,如果划分出来的子串可以用这个字母映射,或者可以建立一个新的字母和字符串的映射关系,我们就继续递归判断下一个pattern中的字母,直到pattern的指针和str的指针同时指到最末
技巧在于,
1. 用HashMap + HashSet来保证一一对应
2. 把HashMap和HashSet用作instance variable, 甚至boolean result也可用作instance variable, 这样任何在递归调用函数里所做的改变,都会保留,而不用把HashMap, HashSet, result加入递归argument
1 public class Solution { 2 HashMap<Character, String> map = new HashMap<Character, String>(); 3 HashSet<String> set = new HashSet<String>(); 4 5 6 public boolean wordPatternMatch(String pattern, String str) { 7 if (pattern==null || str==null) return false; 8 return helper(pattern, str, 0, 0); 9 } 10 11 public boolean helper(String pattern, String str, int i, int j) { 12 if (i==pattern.length() && j==str.length()) { 13 return true; 14 } 15 if (i==pattern.length() || j==str.length()) return false; 16 char key = pattern.charAt(i); 17 for (int cut=j+1; cut<=str.length(); cut++) { 18 String trial = str.substring(j, cut); 19 if (!map.containsKey(key) && !set.contains(trial)) { // ensure one-on-one matching 20 map.put(key, trial); 21 set.add(trial); 22 if (helper(pattern, str, i+1, cut)) 23 return true; 24 map.remove(key); 25 set.remove(trial); 26 } 27 else if (map.containsKey(key) && map.get(key).equals(trial)) { 28 if (helper(pattern, str, i+1, cut)) 29 return true; 30 } 31 } 32 return false; 33 } 34 }