Word Pattern

Word Pattern

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

"Follows" means there is a bijection (one-to-one mapping) between each letter in pattern and each non-empty word in s. Specifically:

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

Examples

Example 1:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Explanation: 'a' -> "dog", 'b' -> "cat". The mapping is consistent.

Example 2:

Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Explanation: 'a' maps to "dog" at index 0 but would need to map to "fish" at index 3.

Example 3:

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
Explanation: 'a' would need to map to both "dog" and "cat".

Constraints

• 1 <= pattern.length <= 300
• pattern contains only lowercase English letters.
• 1 <= s.length <= 3000
• s contains only lowercase English letters and spaces.
• s has no leading or trailing spaces.
• Words in s are separated by a single space.

Expected Complexity

• Time: O(n + m) where n is the pattern length and m is the string length
• Space: O(n) for the mappings