algoadvance

Leetcode 290. Word Pattern

Problem Statement

You are given a pattern s and a string str. Determine if str follows the same pattern.

Here is the problem statement in more detail:

• pattern is a string containing only lowercase alphabetical characters.
• str is a string containing lowercase alphabetical words separated by spaces.

• Determine if str follows the same pattern where:

  • Each unique character in pattern corresponds to a unique word in str.
  • Each unique word in str must match a unique character in pattern.

Example

• Input: pattern = “abba”, str = “dog cat cat dog” Output: true

• Input: pattern = “abba”, str = “dog cat cat fish” Output: false

• Input: pattern = “aaaa”, str = “dog cat cat dog” Output: false

• Input: pattern = “abba”, str = “dog dog dog dog” Output: false

Clarifying Questions

1. Can pattern or str be empty?
   • No, both pattern and str are non-empty.
2. Are words in str separated by exactly one space?
   • Yes, the words in str are separated by exactly one space.

Strategy

To solve this problem, we can use two hash maps (or dictionaries):

• One map for pattern-to-word.
• One map for word-to-pattern.

We will iterate through the pattern and the words in str simultaneously, checking if the current pattern character and current word adhere to the expected mapping. If we find a contradiction at any point, we return false.

Code

import java.util.HashMap;

public class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        
        if (pattern.length() != words.length) {
            return false;
        }
        
        HashMap<Character, String> patternToWordMap = new HashMap<>();
        HashMap<String, Character> wordToPatternMap = new HashMap<>();
        
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            String word = words[i];
            
            if (patternToWordMap.containsKey(c)) {
                // Check if the current character's mapped word matches the current word
                if (!patternToWordMap.get(c).equals(word)) {
                    return false;
                }
            } else {
                patternToWordMap.put(c, word);
            }
            
            if (wordToPatternMap.containsKey(word)) {
                // Check if the current word's mapped pattern character matches the current character
                if (wordToPatternMap.get(word) != c) {
                    return false;
                }
            } else {
                wordToPatternMap.put(word, c);
            }
        }
        return true;
    }
}

Time Complexity

• Splitting the string s: O(n), where n is the length of the string s.
• Looping through the pattern: O(m), where m is the length of the pattern.
• HashMap operations (put/get): O(1) on average.

Thus, the overall time complexity is O(n + m). Given that m is typically proportional to n (the words in str), the time complexity can be considered O(n).

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?