![Word Pattern Leetcode Problem 290 [Python Solution]](https://auditorical.com/wp-content/uploads/2023/10/Word-Pattern-Leetcode-Problem-290-Python-Solution-1.webp)
Word Pattern Leetcode Problem 290 [Python Solution]
In this blog post, we’ll tackle the Word Pattern LeetCode problem (Problem 290) under the category of Arrays & Hashing.
The objective is to determine whether a given pattern matches a provided string.
Matching, in this context, means establishing a bijection between the characters in the pattern and the non-empty words in the string.
Example 1:
Let’s take an example to clarify the problem.
Given a pattern abba and a string dog cat cat dog, we need to determine if the string follows the pattern.
The expected output in this case is true.
Example 2:
Another example: pattern abba and string dog cat cat fish.
The expected output is false.
Example 3:
Pattern aaaa and string dog cat cat dog results in an output of false.
Constraints:
Before we dive into the solution, let’s establish the constraints:
- The length of the pattern is in the range 1 to 300.
- The pattern consists of lowercase English letters.
- The length of string
sis in the range 1 to 3000. - The string
scontains only lowercase English letters and spaces. sdoes not have leading or trailing spaces.- Words in
sare separated by a single space.
Now that we understand the problem statement and constraints, let’s proceed to the solution.
Understanding Bijection Constraints
The core idea of this problem is to establish a bijection between characters in the pattern and words in the string.
A bijection implies a one-to-one mapping: each character maps to a unique word, and each word maps to a unique character.
Word Pattern LeetCode Problem Solution
Now let’s delve into the Python solution for the Word Pattern problem.
We will discuss both a brute-force approach and a more efficient solution.
1. Bruteforce Approach
def wordPattern(self, pattern: str, s: str) -> bool:
words = s.split(" ")
if len(pattern) != len(words):
return False
charToWord = {}
wordToChar = {}
for c, w in zip(pattern, words):
if c in charToWord and charToWord[c] != w:
return False
if w in wordToChar and wordToChar[w] != c:
return False
charToWord[c] = w
wordToChar[w] = c
return TrueIn the brute-force approach, we start by splitting the string s into words, using the space character as a separator.
We then check if the lengths of the pattern and words match; if they don’t, we return False immediately.
We maintain two dictionaries: charToWord to map characters to words and wordToChar to map words to characters.
As we iterate through the pattern and words simultaneously, we check for conflicts in the mappings.
If a character or word has already been assigned to a different mapping, we return False.
If not, we update the mappings.
2. An Efficient Approach with HashMap
The brute-force approach is simple and understandable, but it can be optimized.
An efficient approach would be to use two hash maps to store the mappings and perform the checks without iterating through the entire pattern and words.
def wordPattern(self, pattern: str, s: str) -> bool:
words = s.split(" ")
if len(pattern) != len(words):
return False
charToWord = {}
wordToChar = {}
for c, w in zip(pattern, words):
if (c in charToWord and charToWord[c] != w) or (w in wordToChar and wordToChar[w] != c):
return False
charToWord[c] = w
wordToChar[w] = c
return True
This optimized approach works similarly to the brute-force approach, but it includes the checks for conflicts directly within the loop.
If a conflict is found, we return False.
Otherwise, we update the mappings as before.
Time and Space Complexity
The time complexity of this solution is O(n), where n is the total number of characters in the pattern and string s.
This is because we iterate through both of them once.
The space complexity is also O(n) since we use two hash maps to store the mappings, and the space required is directly proportional to the input size.
Reasoning Behind Our Approach
We’ve discussed the approach, but it’s important to understand why it works.
By maintaining two mappings, we ensure that each character in the pattern corresponds to a unique word and vice versa.
If any conflict arises during the mapping, we immediately return False, indicating that the pattern and string do not match.
Otherwise, we return True.
Related Interview Questions By Company:
Related Interview Questions By Difficulty:
Related Interview Questions By Category:
- Boats To Save People LeetCode
- Kth Smallest Element In A BST LeetCode
- Kth Largest Element In A Stream LeetCode
Conclusion
In this blog post, we’ve explored the Word Pattern LeetCode problem, which involves establishing a bijection between characters in a pattern and words in a string.
We’ve discussed both a brute-force and an efficient approach, with the optimized solution using hash maps to efficiently check for conflicts.
Remember that the key to solving this problem is ensuring that both the character-to-word and word-to-character mappings are one-to-one.
If you have any questions, suggestions, or comments, feel free to share them below.
Happy coding!
Now, I encourage you to comment, ask questions, make suggestions, and share this content with others to help them understand and solve the Word Pattern problem on LeetCode.
