easy Word Pattern

Problem Statement

Given a pattern and a string s, return true if the string s follows the same pattern.

Here, the following the pattern means each character in the pattern should map to a single word in s, and each word in s should map to a single character in the pattern.

Examples

Example 1:

• Input: pattern = "eegg", s = "dog dog cat cat"
• Output: true
• Explanation: The pattern "eegg" corresponds to the words "dog dog cat cat". Both 'e's map to "dog" and both 'g's map to "cat".

Example 2:

• Input: pattern = "abca", s = "one two three four"
• Output: false
• Explanation: Here, a maps to the "one" and "four" both. So, the string doesn't follow the same pattern.

Example 3:

• Input: pattern = "abacac", s = "dog cat dog mouse dog mouse"
• Output: true
• Explanation: The pattern "abacac" corresponds to the words "dog cat dog mouse dog mouse". 'a' maps to "dog", 'b' maps to "cat", and 'c' maps to "mouse".

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

To solve this problem, we need to establish a one-to-one correspondence between each character in the pattern and each word in the string s. This can be effectively managed using two hash maps: one to map characters from the pattern to words in s, and another to map words in s to characters in the pattern. This dual mapping ensures that the relationship is consistent in both directions. If at any point we find that a character or word does not map as expected, we can conclude that string does not follow the pattern.

This approach is efficient because it allows us to quickly check and establish the required mappings. The use of hash maps ensures that our checks and insertions are done in constant time on average, making the overall approach fast and reliable.

Step-by-step Algorithm

1. Split the string s into an array of words.
2. Check if the length of the pattern matches the number of words in s. If not, return false.
3. Initialize two hash maps: one for pattern to word mapping (char_to_word), and one for word to pattern mapping (word_to_char).
4. Iterate over each character in the pattern and the corresponding word in s:
   • Check if the character is already mapped:
     • If it is, ensure it maps to the current word.
     • If it does not match, return false.
   • Else, add character and word to 'char_to_word' map.
   • Check if the word is already mapped:
     • If it is, ensure it maps to the current character.
     • If it does not match, return false.
   • Else, add word and character to 'word_to_char' map.
5. Return true if all characters and words map correctly.

Algorithm Walkthrough

Input: pattern = "abacac", s = "dog cat dog mouse dog mouse"

1. Initial Input:

   • Pattern: abacac
   • String s: dog cat dog mouse dog mouse

2. Step 1: Split the string s into words:

   • Words: ["dog", "cat", "dog", "mouse", "dog", "mouse"]

3. Step 2: Check length:

   • Length of pattern: 6
   • Number of words: 6
   • Lengths match, proceed to the next step.

4. Step 3: Initialize hash maps:

   • charToWord = {}
   • wordToChar = {}

5. Step 4: Iterate over each character and word:

   • Iteration 1:

     • Character: a
     • Word: dog
     • a is not in charToWord, and dog is not in wordToChar.
     • Map a to dog: charToWord = {'a': 'dog'}
     • Map dog to a: wordToChar = {'dog': 'a'}

   • Iteration 2:

     • Character: b
     • Word: cat
     • b is not in charToWord, and cat is not in wordToChar.
     • Map b to cat: charToWord = {'a': 'dog', 'b': 'cat'}
     • Map cat to b: wordToChar = {'dog': 'a', 'cat': 'b'}

   • Iteration 3:

     • Character: a
     • Word: dog
     • a is in charToWord, and it maps to dog.
     • dog is in wordToChar, and it maps to a.
     • Mappings are consistent, proceed to the next iteration.

   • Iteration 4:

     • Character: c
     • Word: mouse
     • c is not in charToWord, and mouse is not in wordToChar.
     • Map c to mouse: charToWord = {'a': 'dog', 'b': 'cat', 'c': 'mouse'}
     • Map mouse to c: wordToChar = {'dog': 'a', 'cat': 'b', 'mouse': 'c'}

   • Iteration 5:

     • Character: a
     • Word: dog
     • a is in charToWord, and it maps to dog.
     • dog is in wordToChar, and it maps to a.
     • Mappings are consistent, proceed to the next iteration.

   • Iteration 6:

     • Character: c
     • Word: mouse
     • c is in charToWord, and it maps to mouse.
     • mouse is in wordToChar, and it maps to c.
     • Mappings are consistent.

6. Step 5: All characters and words are mapped correctly.

   • Return true.

Code

import java.util.HashMap;

class Solution {

  public boolean wordPattern(String pattern, String s) {
    // Split the string s into words
    String[] words = s.split(" ");
    // If lengths of pattern and words do not match, return false
    if (pattern.length() != words.length) {
      return false;
    }

    // Initialize hash maps to keep track of mappings
    HashMap<Character, String> charToWord = new HashMap<>();
    HashMap<String, Character> wordToChar = new HashMap<>();

    // Iterate over each character and word
    for (int i = 0; i < pattern.length(); i++) {
      char c = pattern.charAt(i);
      String word = words[i];

      // Check if the character is already mapped
      if (charToWord.containsKey(c)) {
        // If mapped word doesn't match the current word, return false
        if (!charToWord.get(c).equals(word)) {
          return false;
        }
      } else {
        // Map the character to the word
        charToWord.put(c, word);
      }

      // Check if the word is already mapped
      if (wordToChar.containsKey(word)) {
        // If mapped character doesn't match the current character, return false
        if (wordToChar.get(word) != c) {
          return false;
        }
      } else {
        // Map the word to the character
        wordToChar.put(word, c);
      }
    }

    // If all checks pass, return true
    return true;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Example 1
    System.out.println(solution.wordPattern("eegg", "dog dog cat cat")); // true
    // Example 2
    System.out.println(solution.wordPattern("abca", "one two three four")); // false
    // Example 3
    System.out.println(
      solution.wordPattern("abacac", "dog cat dog mouse dog mouse")
    ); // true
  }
}

Complexity Analysis

• Time Complexity: , where n is the length of the pattern or the number of words in s. We iterate through the pattern and the words once, performing constant-time operations (hash map lookups and insertions) at each step.
• Space Complexity: , where n is the number of unique characters in the pattern or unique words in s. In the worst case, we store every character and word in the hash maps.