#291 Word Pattern II

Dropbox phone interview面經題。

input是兩個字串：pattern和str。

str是字串，pattern是字母組合，裡的每個字母代表幾個字母組成的字串

例如：str = "redblueredblue", pattern = "abab", 則a=red, b=blue.

output是判斷str是否符合pattern，return true or false.

這題要用backtracking來解。

概念上就是

redblueredblue a - r 記到map中

redblueredblue b - e 記到map中

redblueredblue a - d 發現和map記錄不合

redblueredblue b - ed 記到map中

redblueredblue a - b 發現和map記錄不合

...

redblueredblue b - edblue 記到map中

redblueredblue a - r 和map吻合

redblueredblue b - edblue 字串和map吻合，尋找完畢。

宣告一個Map來存pattern-string的mapping table，

和一個Set來存已經有對應pattern的string，避免有不同pattern對到相同的string。

Map<Character, String> map = new HashMap<>();
Set<String> set = new HashSet<>();

接下來寫一個function: isMatch，裡面要做的事情是：

讀取一個pattern字母，看他是否在Map中，

若有，看目前的string位置是否可以找到該字母對應的字串，若可以，看下一個pattern。

若沒有，將當前pattern-string pair存到Map中，看下一個pattern。

完整程式碼：

public class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        //create a Map to save pattern-string mapping table
        //create a Set to save strings to avoid mapping same string to different pattern
        //call function isMatch(str, 0, pattern, 0, Map, Set)
        Map<Character, String> map = new HashMap<>();
        Set<String> set = new HashSet<>();
        return isMatch(str, 0, pattern, 0, map, set);
    }

    //function: isMatch(str, 0, pattern, 0, Map, Set)
    //  if(i==str.length && j == pattern.length) return true;
    //  if(i==str.length || j == pattern.length) return false;
    //  get current pattern c
    //  check if this pattern is already saved in map
    //  if yes, get the string corresponding to c -> s
    //          use str.startswith(s, i) to check if s can be found
    //  if no, enter a loop for backtracking, for(k=i; k<str.length(); k++)
    //         String p = str.substring(i, k + 1);
    //         if set contains p, this p can't match to another pattern, so continue.
    //         put (c,p) into map and put p into set
    //         continue to match the rest by calling if(isMatch(str, k+1, pattern, j+1, map, set)) return true;
    //         if can't match, remove (c,p) from map, and remove p from set
    //  after getting out the loop, we tried all pattern-substring combinations but still fail to match. return false
    boolean isMatch(String str, int i, String pattern, int j, Map<Character, String> map, Set<String> set){
        if(i==str.length() && j == pattern.length()) return true;
        if(i==str.length() || j == pattern.length()) return false;

        char c = pattern.charAt(j);
        if(map.get(c)!=null){
            String s = map.get(c);
            if(!str.startsWith(s, i)){
                return false;
            }

            return isMatch(str, i+s.length(), pattern, j+1, map, set);
        }
        else{
            for(int k=i; k<str.length(); k++){
                String p = str.substring(i, k + 1);
                if(set.contains(p)){
                    continue;
                }
                map.put(c,p);
                set.add(p);
                if(isMatch(str, k+1, pattern, j+1, map, set)) 
                    return true;

                map.remove(c);
                set.remove(p);
            }
            return false;
        }
    }
}