Skip to content

Word Pattern⚓︎

Link

Description⚓︎

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.

Solution⚓︎

Solution 1⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    bool wordPattern(string pattern, string s) {
        vector<string> words;
        string sub_s = "";

        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                words.push_back(sub_s);
                sub_s = "";
            } else {
                sub_s += s[i];
            }
        }
        words.push_back(sub_s);

        if (pattern.size() != words.size()) return false;

        unordered_map<char, string> patternToWord;
        unordered_set<string> wordSet;

        for (int i = 0; i < pattern.size(); i++) {
            char c = pattern[i];
            string word = words[i];
            if (!patternToWord.count(c)) {
                if (wordSet.count(word)) return false;
                patternToWord[c] = word;
            } else {
                if (patternToWord[c] != word) return false;
            }

            wordSet.insert(word);
        }

        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    bool wordPattern(string pattern, string s) {
        vector<string> words;
        stringstream tokenStream(s);
        string word;
        while (tokenStream >> word) words.emplace_back(word);

        if (words.size() != pattern.size()) return false;

        unordered_map<char, string> patternToWord;
        unordered_map<string, char> wordToPattern;

        for (int i = 0; i < pattern.size(); i++) {
            auto from = pattern[i];
            auto to = words[i];

            if (patternToWord.count(from) && patternToWord[from] != to)
                return false;
            patternToWord[from] = to;

            if (wordToPattern.count(to) && wordToPattern[to] != from)
                return false;
            wordToPattern[to] = from;
        }

        return true;
    }
};
  • Time complexity: \(O(n + m)\);
  • Space complexity: \(O(n + m)\).

Solution 3⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool wordPattern(string pattern, string s) {
        unordered_map<char, int> patternMap;
        unordered_map<string, int> wordMap;

        istringstream iss(s);
        vector<string> words;
        string word;
        while (iss >> word) words.emplace_back(word);

        if (words.size() != pattern.size()) return false;

        for (int i = 0; i < words.size(); i++) {
            char c = pattern[i];
            string w = words[i];
            if (!patternMap.count(c)) patternMap[c] = i;
            if (!wordMap.count(w)) wordMap[w] = i;

            if (patternMap[c] != wordMap[w]) return false;
        }
        return true;
    }
};