[Leetcode 290] Word Pattern （Eas

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 word in str.

Example 1:

Input: pattern = "abba", str = "dog cat cat dog"
Output: true

Example 2:

Input:pattern = "abba", str = "dog cat cat fish"
Output: false

Example 3:

Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false

Example 4:

Input: pattern = "abba", str = "dog dog dog dog"
Output: false

Notes:

• You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.

Solution

1. 题目要求的是找是否有匹配， 且bijection between a letter in pattern and a non-empty word in str.。 所以采用2个Map，

        Map<String, String> pattern2Str = new HashMap<> ();
        Map<String, String> str2Pattern = new HashMap<> ();

2. 首先将str用space split得到一个List，判断pattern的长度和strList长度是否一致，不一致就肯定不是same pattern，直接返回false
3. 然后用一个loop同时扫描pattern和strList， 判断二者是否follow same pattern
   • 如果pattern2Str和str2Pattern2个map都不包含sub pattern 和sub String，那么就写入Map。
   • 如果任一一个包含，那么就判断pattern2Str中对应的str value是否与当前sub String相同，不同则不是same pattern，直接返回false。
   • 同时，因为是双向匹配的，所以必须同时判断str2Pattern中对应的pattern value是否与当前sub pattern相同，不同则不是same pattern，直接返回false。

E.g "abba", str = "dog cat cat fish"
pattern2Str: , Str2Pattern:
index = 0, 写入a : dog ----- dog: a
index = 1, 写入b : cat ----- cat: b
index = 2, pattern2Str中key == b, value == cat, 与str[2] == cat符合， 反之也吻合
index = 3, pattern2Str中key == a, value ==dog, 与str[3] == fish不吻合。返回false

或者用一个map也可以解决

1. Map<pattern, String>: 如果map中没有包含pattern，那么应该写入map；但是如果此时的String已经在map中了，那么就是 "ab", "cat, cat"这种情况，返回false
2. 如果map中包含pattern，判断map中的String与list中的String是否吻合，不吻合则返回false

class Solution {
    public boolean wordPattern(String pattern, String str) {
//         String[] words = str.split (" ");
//         if (words.length != pattern.length ()) {
//             return false;
//         }
        
//         Map<String, String> tracker = new HashMap<> ();
        
//         for (int i = 0; i < words.length; i++) {
//             if (!tracker.containsKey (pattern.substring(i, i + 1))) {
//                 if (tracker.containsValue (words [i])) {
//                     return false;
//                 }
                
//                 tracker.put (pattern.substring(i, i + 1), words[i]);
//             } else {
//                 if (!tracker.get (pattern.substring (i, i + 1)).equals (words[i])) {
//                     return false;
//                 }
//             }
//         }

//         return true;
//     }
        
        String[] strList = str.split (" ");
        if (strList.length != pattern.length ()) {
            return false;
        }
        
        Map<String, String> pattern2Str = new HashMap<> ();
        Map<String, String> str2Pattern = new HashMap<> ();
        
        for (int i = 0; i < pattern.length (); i++) {
            String patternEntry = pattern.substring (i, i + 1);
            String strEntry = strList [i];
            
            if (!pattern2Str.containsKey (patternEntry) && !str2Pattern.containsKey (strEntry)) {
                pattern2Str.put (patternEntry, strEntry);
                str2Pattern.put (strEntry, patternEntry);
            }
            
            if (!pattern2Str.getOrDefault(patternEntry, "").equals (strEntry) || !str2Pattern.getOrDefault (strEntry, "").equals (patternEntry)) {
                return false;
            }
        }
        
        return true;
    }
}