LeetCode: 290-Word Pattern 解題紀錄

Last Updated on 2022-01-17 by Clay

題目

Given a pattern and a string s, find if s 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 s.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= pattern.length <= 300
• pattern contains only lower-case English letters.
• 1 <= s.length <= 3000
• s contains only lowercase English letters and spaces ' '.
• s does not contain any leading or trailing spaces.
• All the words in s are separated by a single space.

題目給定兩組字串，第一組是 pattern（樣例，模板之類的意思），是某個特定的組合，比方說 abba；另一組輸入字串，比方說 "dog cat cat dog"，這樣就是符合 pattern，因為如果我們把 dog 視為 a、cat 視為 b，也會同樣是 abba 的 pattern —— 這種情況，我們回傳 true。

反之，若是另外一組輸入字串是 "dog cat cat fish"，那麼就不符合 pattern 了。

---

解題思路

首先，我將輸入字串以空白隔開（這樣會區分出一個個的詞），接著按照順序，將該詞對應到同樣 index 的 pattern 的字元。

假設我的 tokens 是一個列表（實際上為了節省記憶體所以不是，不過可以假設它是）那麼 tokens[i] 對應 pattern[i]，如果 tokens[i] 已經存在於對應關係表但是對應關係表儲存的字元不對應當前的 pattern[i]，那麼輸入字串很明顯不對應 pattern，返回 false。

另外就是不同的詞對應同一個 pattern 字元，那很顯然也不對應 pattern。

比方說以 Example 2 而言，我解題的過程可以理解為：

pattern: "abba"
tokens: [dog, cat, cat, fish]

i=0, s[0]="dog", pattern[0]='a':
s2p = [
    dog => a
]

i=1, s[1]="cat", pattern[1]='b':
s2p = [
    dog => a
    cat => b
]

i=2, s[2]="cat", pattern[2]='b':
s2p = [
    dog => a
    cat => b
]

i=3, s[3]="fish", pattern[3]='a':
s2p = [
    dog => a
    cat => b
    fish => a  <------------- Error!
]

只有一切都沒有發生錯誤地走到最後，才會回傳 true。

複雜度

Time Complexity	O(n)
Space Complexity	O(n)

C++ 範例程式碼

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        // Init
        int i = 0;
        unordered_map<string, char> s2p;
        istringstream tokens(s);
        string token;
        
        // token is a word split by space ' '
        while (getline(tokens, token, ' ')) {
            // If token exist in s2p, check the corresponding pattern[i], if it's different, return false
            if (s2p.find(token) != s2p.end()) {
                if (s2p[token] != pattern[i]) return false; 
            }
            
            // If the new token mapping to a exist value, it means the pattern is not match, return false
            else {
                for (auto item: s2p) {
                    if (item.second == pattern[i]) return false;
                }
                s2p[token] = pattern[i];
            }
            ++i;
        }
        
        // If the i less than pattern size, it means the pattern not match
        if (i != pattern.size()) return false;
        
        return true;        
    }
};

Python 範例程式碼

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        # Init
        i = 0
        s2p = dict()
        tokens = s.split()
        
        # If length not match
        if (len(tokens) != len(pattern)): return False
    
        # Match
        for i in range(len(tokens)):
            # If token exist in s2p, check the corresponding pattern[i], if it's different, return false
            if tokens[i] in s2p:
                if s2p[tokens[i]] != pattern[i]: return False
            
            # If the new token mapping to a exist value, it means the pattern is not match, return false
            else:
                for key in s2p:
                    if s2p[key] == pattern[i]: return False
                
                s2p[tokens[i]] = pattern[i]
                
        return True

---

References

• https://leetcode.com/problems/word-pattern/

---

Read More

LeetCode 解題紀錄目錄