algoadvance

Leetcode 290. Word Pattern

Problem Statement

1. Word Pattern

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

Example 4:

Input: pattern = "abba", s = "dog dog dog 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.

Clarifying Questions

1. Are there multiple spaces between words in s?
   • No, s is well-formatted with a single space separating the words.
2. Do we need to consider letter case variations (e.g., “Dog” vs “dog”)?
   • No, the problem statement specifies that s contains only lowercase English letters.
3. Is an empty s or pattern possible?
   • No, given constraints assure the length of pattern is between 1 and 300 and s between 1 and 3000.

Strategy

1. Split the string s into individual words.
2. Check the length of the pattern and the list of words derived from s. If they do not match, return false.
3. Use two hash maps (dictionaries):
   • patternToWord to map each character in the pattern to a corresponding word in s.
   • wordToPattern to map each word in s to a corresponding character in the pattern.
4. Loop through the pattern and the words simultaneously:
   • If a character in the pattern is already mapped but does not map to the current word or vice versa, return false.
   • If no conflicts arise, map the character to the word and the word to the character.
5. If the loop completes without conflicts, return true.

Code

#include <iostream>
#include <unordered_map>
#include <vector>
#include <sstream>
using namespace std;

bool wordPattern(string pattern, string s) {
    // Split s into words
    vector<string> words;
    stringstream ss(s);
    string word;
    while (ss >> word) {
        words.push_back(word);
    }

    // If pattern length and words' length doesn't match
    if (pattern.length() != words.size()) return false;

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

    for (int i = 0; i < pattern.length(); i++) {
        char p = pattern[i];
        string w = words[i];

        // Check if there is a conflict in pattern to word mapping
        if (patternToWord.count(p) > 0 && patternToWord[p] != w) return false;
        if (wordToPattern.count(w) > 0 && wordToPattern[w] != p) return false;

        // Establish new mapping
        patternToWord[p] = w;
        wordToPattern[w] = p;
    }

    return true;
}

int main() {
    string pattern = "abba";
    string s = "dog cat cat dog";
    cout << (wordPattern(pattern, s) ? "true" : "false") << endl;  // Output: true
    return 0;
}

Time Complexity

• Splitting the string s: O(n), where n is the length of s.
• Loop through the pattern and words: O(m), where m is the length of the pattern.
• Overall Time Complexity: O(n + m), realistically O(n), considering m is significantly smaller than n.

This code and strategy ensure the solution is efficient and clear.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?