290 Word Pattern
Given a
pattern
and a stringstr
, find ifstr
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 instr
.Examples:
- 1.pattern =
"abba"
, str ="dog cat cat dog"
should returntrue
. - 2.pattern =
"abba"
, str ="dog cat cat fish"
should returnfalse
. - 3.pattern =
"aaaa"
, str ="dog cat cat dog"
should returnfalse
. - 4.pattern =
"abba"
, str ="dog dog dog dog"
should returnfalse
.
Notes:
You may assume
pattern
contains only lowercase letters, andstr
contains lowercase letters separated by a single space.The Idea: Use a bidirectional map to check for a one to one mapping between each character in the pattern and each word in the sentence.
Complexity: O(n) time and O(2n) space:
def wordPattern(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
if len(pattern) != len(str.split()):
return False
chars_word = {}
word_char = {}
for char, word in zip(pattern, str.split()):
if (chars_word.__contains__(char) and chars_word[char] != word)\
or word_char.__contains__(word) and word_char[word] != char:
return False
elif not chars_word.__contains__(char):
chars_word[char] = word
word_char[word] = char
return True
Last modified 4yr ago