Word Pattern

Problem Description

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. Specifically:

• Each letter in pattern maps to exactly one unique word in s.
• Each unique word in s maps to exactly one letter in pattern.
• No two letters map to the same word, and no two words map to the same letter.

Key Insights

• We need to establish a one-to-one relationship between characters in the pattern and words in the string s.
• Use two hash tables (or dictionaries) for tracking the mappings: one for characters to words and another for words to characters.
• The string s should be split into words, and the number of words must match the length of the pattern.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. We iterate through the string and the pattern once. Space Complexity: O(m), where m is the number of unique characters in the pattern or unique words in s.

Solution

To solve this problem, we will use two hash tables:

1. The first hash table will map characters from the pattern to words in s.
2. The second hash table will map words in s to characters in the pattern.

We will iterate through both the pattern and the split string s. For each character in pattern and the corresponding word in s, we will check the existing mappings in both hash tables. If any mapping is inconsistent, we return false. If we successfully map all characters and words, we return true.

Code Solutions