Vultr DocsLatest Content

Word Pattern

Updated on 01 July, 2025
Word Pattern header image

Problem Statement

The task is to determine if a given string s follows the same pattern defined by another string pattern. The string s must match the pattern such that a letter from pattern corresponds exactly and exclusively to a non-empty word in s. This challenge requires establishing a bijection, meaning:

  • Each letter in pattern should map to one unique word in s.
  • Each word in s should correspond to one unique letter in pattern.
  • The relationship between letters and words should be consistent throughout the string and pattern; no letter can map to more than one word, and no word can map to more than one letter.

This clearly defined relationship should hold for the entirety of both the pattern and s.

Examples

Example 1

Input:

pattern = "abba", s = "dog cat cat dog"

Output:

true

Explanation:

The bijection can be established as:

* `'a'` maps to `"dog"`.
* `'b'` maps to `"cat"`.

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.

Approach and Intuition

To determine if "s" follows the described pattern:

  1. First, split string s into individual words based on spaces, as each word will potentially map to a letter in pattern.

  2. Check if the number of words in s matches the length of pattern. If they do not match, it is impossible for s to follow the pattern.

  3. Utilize two hash maps to ensure the bijection, where:

    • One maps characters from pattern to words in s.
    • The other maps words in s back to characters from pattern.

  4. Iterate over each letter in pattern and the corresponding word in s (obtained from splitting):

    • For each mapping:
      • If a letter in pattern is seen for the first time, map it to the current word in s. Simultaneously, map the word in s to the letter in pattern.
      • If a letter or a word is repeatedly seen, check their mappings. If any of the current mappings disagree with previously established mappings, return false indicating that s does not follow pattern.

  5. If you successfully navigate the entire pattern without conflicts in mapping, return true.

Considerations Based on Given Examples

  • Consider how words match with characters and how variations from these allocations lead to a false outcome. For example,
    • If two different characters in pattern map to the same word in s, it breaks the rule of bijection.
    • Similarly, if a single character is supposed to map to different words at different occurrences, it signifies a violation of the pattern rule.

Using hash maps allows for an efficient check of these relationships while iterating through both the pattern and the string only once, ensuring a time complexity that is linear relative to the size of s and pattern.

Solutions

  • Java
  • Python
java 
class Solution {
    public boolean isPatternMatching(String pat, String str) {
        HashMap patternMap = new HashMap();
        String[] words = str.split(" ");
    
        if (words.length != pat.length())
            return false;
    
        for (Integer index = 0; index < words.length; index++) {
            char p = pat.charAt(index);
            String word = words[index];
    
            if (!patternMap.containsKey(p))
                patternMap.put(p, index);
    
            if (!patternMap.containsKey(word))
                patternMap.put(word, index);
    
            if (patternMap.get(p) != patternMap.get(word))
                return false;
        }
    
        return true;
    }
}

The given Java code defines a method to determine if a string follows a specific pattern. The method isPatternMatching accepts two strings, pat and str, where pat is a pattern of characters and str is a string of words separated by spaces.

Here’s a breakdown of how the code works:

  • A HashMap called patternMap is initialized to store the relationship between the characters in the pattern and the words in the string.
  • The string str is split into an array of words.
  • If the number of words in str does not match the length of pat, the method returns false immediately.
  • A loop iterates through each character of the pattern:
    • For each character p and the corresponding word from str, the code checks if both are already present in patternMap.
    • If p or the word is not present in the map, it gets added with its current index as the value.
    • The method checks if the indices stored for p and the word in patternMap match. If they differ, false is returned.
  • If all pattern and word pairs have the same mapping throughout the loop, the method returns true.

This approach uses the properties of a HashMap to ensure that each character in the pattern consistently maps to the same word in the string and vice versa, thus determining if str follows the pattern described in pat.

python 
class Solution:
    def isPatternMatch(self, pattern: str, string: str) -> bool:
        index_map = {}
        string_words = string.split()
            
        if len(pattern) != len(string_words):
            return False
            
        for index in range(len(string_words)):
            pattern_char = pattern[index]
            current_word = string_words[index]
    
            key_char = 'char_{}'.format(pattern_char)
            key_word = 'word_{}'.format(current_word)
                
            if key_char not in index_map:
                index_map[key_char] = index
                
            if key_word not in index_map:
                index_map[key_word] = index
                
            if index_map[key_char] != index_map[key_word]:
                return False
            
        return True

The "Word Pattern" problem is to determine if a given string follows a specific pattern. This solution is implemented in Python. Here's a summary of how the code tackles the problem:

  • Initializes an empty dictionary index_map to track mappings between pattern characters and words in the string.
  • Splits the input string into words using split() method and stores them in string_words.
  • Verifies if the number of characters in the pattern is the same as the number of words in the string. If they differ, the function returns False immediately as the pattern cannot be matched.
  • Iterates through the characters in the pattern and the corresponding words in string_words.
    • For each character and word, creates a unique key by combining the character or word with a prefix (char_ for characters and word_ for words).
    • Checks if the keys exist in index_map. If a key does not exist, it maps the key to its current index.
    • Compares the indices mapped to each pattern character and the corresponding word. If they differ at any point, it indicates a mismatch in the pattern mapping, thus the function returns False.
  • If the loop completes without finding mismatches, it returns True, indicating the pattern matches the string words.

This method effectively checks pattern consistency using indexed mapping, ensuring that both pattern characters and words in the string correlate directly to the same indices throughout the sequence.

Comments