Word Pattern

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

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;
    }
}

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