Practice/Google/Leetcode 290. Word Pattern

Leetcode 290. Word Pattern

CodingMust

Problem

You are given a pattern string containing lowercase letters and a string s containing words separated by single spaces. Determine whether there exists a bijective (one-to-one and onto) correspondence between the characters in the pattern and the words in s.

A valid bijection means:

• Each character in the pattern maps to exactly one unique word in s
• Each word in s maps to exactly one unique character in the pattern
• The mapping preserves the order of appearance

Return true if such a bijection exists, otherwise return false.

Requirements

1. Check if the number of characters in the pattern matches the number of words in s
2. Ensure each pattern character consistently maps to the same word throughout
3. Ensure no two different pattern characters map to the same word
4. Maintain the sequential order when applying the mapping

Constraints

• 1 ≤ pattern.length ≤ 300
• pattern contains only lowercase English letters
• 1 ≤ s.length ≤ 3000
• s contains only lowercase English letters and spaces
• s does not contain leading or trailing spaces
• All words in s are separated by a single space
• Time complexity should be O(n) where n is the length of the pattern
• Space complexity should be O(n) for storing mappings

Examples

Example 1:

Input: pattern = "abba", s = "dog cat cat dog" Output: true Explanation: The bijection is: a ↔ dog, b ↔ cat Applying the mapping to "abba" gives "dog cat cat dog"

Example 2:

Input: pattern = "abba", s = "dog cat cat fish" Output: false Explanation: Letter 'a' would need to map to both "dog" and "fish", which violates the bijection property.

Example 3:

Input: pattern = "aaaa", s = "dog dog dog dog" Output: true Explanation: Letter 'a' consistently maps to "dog" throughout the entire pattern.

Example 4:

Input: pattern = "abba", s = "dog dog dog dog" Output: false Explanation: Both 'a' and 'b' would map to "dog", violating the one-to-one requirement.