Word Pattern
Source
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.
Java
public class Solution {
public boolean wordPattern(String pattern, String str){
HashMap<Character, String> map1 = new HashMap<Character, String>();
HashMap<String, Character> map2 = new HashMap<String, Character>();
String[] strs = str.split("\\s");
if(pattern.length()!=strs.length) return false;
for(int i=0; i<pattern.length(); i++){
char c = pattern.charAt(i);
if(!map1.containsKey(c)){
if(map2.containsKey(strs[i])){
return false;
}
else{
map1.put(c, strs[i]);
map2.put(strs[i], c);
}
}
else if(!map1.get(c).equals(strs[i])){
return false;
}
}
return true;
}
}
Python
class Solution(object):
def wordPattern(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
pat_to_str = {}
str_to_pat = {}
str = str.split();
if len(pattern)!=len(str):
return False;
for i in range(len(pattern)):
pat = pattern[i]
s = str[i]
if not pat in pat_to_str:
if s in str_to_pat:
return False
else:
pat_to_str[pat]=s
str_to_pat[s]=pat
elif pat_to_str[pat]!=s:
return False
return True