[LeetCode] 290. Word Pattern

290. Word Pattern

• Hardness: \(\color{green}\textsf{Easy}\)
• Ralated Topics: Hash Table、String

一、題目

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 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.

二、分析

三、解題

1. Hash Table

• Time complexity: \(O(n)\)
• Space complexity: \(O(n)\)

vector<string> split(string& str, char del){
    stringstream ss(str);
    string item;
    vector<string> res;
    while (getline(ss, item, del)){
        if (!item.empty()){
            res.push_back(item);
        }
    }
    return res;
}
bool wordPattern(string pattern, string s) {
    unordered_map<char, string> map;
    unordered_set<string> st;
    vector<string> svec = split(s, ' ');                // 將 s 以空白拆開成陣列
    if (pattern.length() != svec.size()) return false;  // 檢查陣列的個數是否與 pattern 的長度相符
    for (int i = 0; i < svec.size(); i++) {
        char& c = pattern[i];
        if (!map.count(c)) {                            // 定義第一次出現的 pattern 
            if (st.count(svec[i])) return false;        // 如果該字串已經被定義過 pattern 則為 false
            map[c] = svec[i];                           // 定義 pattern
            st.insert(svec[i]);                         // 將定義過的字串記錄下來
        } else {
            if (map[c] != svec[i]) return false;        // 定義的 pattern 不符
        }
    }
    return true;
}

回目錄 Catalog