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