[LeetCode 291] 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.

Example 1:

Input: pattern = "abab", str = "redblueredblue"
Output: true

Example 2:

Input: pattern = pattern = "aaaa", str = "asdasdasdasd"
Output: true

Example 3:

Input: pattern = "aabb", str = "xyzabcxzyabc"
Output: false

Notes:

• You may assume both pattern and str contains only lowercase letters.

Solution: Backtracking + Map

1. 与LC290相比，此题给定的String没有事先分出substring，需要自己找合适的substring （用backtracking来找到所有的），同时尝试找是否有good match
2. 需要用Map结构来存储pattern2String的匹配
3. Recursively找substring和good matching
   • 如果Map中没有包含key (pattern) ，此时需要尝试找substring，然后放入到map中，继续recursively看是否能够找到good match，如果一旦找到，那么返回true。如果没有找到，则清除map中已经存入的pattern entry
   • 如果Map中已经包含key (pattern) ，此时需要判断，其在map中对应的String value是否是在remaining substring中起始的位置（该判断就是判断，是否map中的pattern -- String，与substring中的String匹配）。如果不匹配，直接返回false；匹配则继续处理。
   • 整个过程处理完后，如果都没有发现不匹配，则返回true。
4. Base Case：
   • PatternIndex & StringIndex都同时走到了尾部，则说明找到全部匹配，返回true。
   • PatternIndex Or StringIndex 有一个走到了尾部，一个没有。则中说没有找到匹配，返回false

class Solution {
    // 就是backtracking，把每一种可能都拿出来做判断。// you dian yi si!!!!!
    public boolean wordPatternMatch(String pattern, String str) {
        if (pattern == null || str == null || str.length () < pattern.length ())
            return false;
        
        // Map to store the mapping of pattern character and string words
        Map <Character, String> tracker = new HashMap<> ();
        
        // indexOfPattern, indexOfStr, 
        return wordPatternMatchHelper (pattern, str, 0, 0, tracker);
    }
    
    private boolean wordPatternMatchHelper (String pattern, String str, int indexOfPattern, int indexOfStr, Map<Character, String> tracker) {
        // base case: 1. 如果2个指针同时到尾说明找到了，返回true
        if (indexOfPattern == pattern.length () && indexOfStr == str.length ()) {
            return true;
        }
        
        // base case: 2.if only one index reaches the end, another doesn't means, this is not a matching
        if (indexOfPattern == pattern.length () || indexOfStr == str.length ()) {
            return false;
        }
        
        // if both doesn't reach the end, then continue checking
        char patternChar = pattern.charAt (indexOfPattern);
        
        if (tracker.containsKey (patternChar)) {
            String temp = tracker.get (patternChar);
            // check substring of Str starting from indexOfStr is start with the temp
            // 在Str中没有找到，从indexOfstr开始，startWith temp的substring
            if (!str.substring (indexOfStr).startsWith (temp)){
                return false;
            }
                
            // 如果这个pattern对应的substring找到了，那么继续往下找
            return wordPatternMatchHelper (pattern, str, indexOfPattern + 1, indexOfStr + temp.length (), tracker);
            
        } else {
            // try put some substring of str into the map and check if it has good match
            for (int i = indexOfStr; i < str.length (); i++) {
                String temp = str.substring (indexOfStr, i + 1);
                if (tracker.containsValue (temp)) // temp is already has a different key
                    continue;
                
                tracker.put (patternChar, temp);
                if (wordPatternMatchHelper (pattern, str, indexOfPattern + 1, i + 1, tracker)) {
                    return true;
                }
                    
                tracker.remove (patternChar);
            }
        }
        
        return false;
    }
}