leetCode Question: Word Pattern

Word Pattern

Given a pattern and a string str, find if str 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 str.

Examples:
pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Analysis:

This problem is not hard but needs you be more careful with all the conditions:

  • The length of the words in str and chars in pattern may be different
  • The char to word is a bijection, which means it is a one-to-one mapping.
  • Don't forget to handle the last word when you split the str.

Here for the bijection mapping, I just used two maps, one save (word, char), and the other to save (char, word).

Code (C++):

class Solution {
public:
bool wordPattern(string pattern, string str) {
map<char, string> mp1;
map<string, char> mp2;
string tmp = "";
int j = 0;
for (int i=0;i<=str.size();i++){
if (j == pattern.size()){ return false; }
if (str[i]==' ' || i == str.size()){
if (mp1.find(pattern[j]) == mp1.end() && mp2.find(tmp) == mp2.end()){
mp1[pattern[j]] = tmp;
mp2[tmp] = pattern[j++];
}else{
if (mp1[pattern[j]] == tmp && mp2[tmp] == pattern[j]){ j++; }
else{ return false; }
}
tmp = "";
}else{
tmp += str[i];
}
}
if (j != pattern.size()){return false;}
return true;
}
};

Code (Python):

class Solution(object):
def wordPattern(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
mp1 = {}
mp2 = {}
words = str.split(' ')
if len(words)!=len(pattern):
return False
for word, ch in zip(words, pattern):
if word not in mp1 and ch not in mp2:
mp1[word] = ch
mp2[ch] = word
elif mp1.get(word) == ch and mp2.get(ch) == word:
pass
else:
return False
return True

No comments:

Post a Comment