Title: Word Pattern Source: leetcode.com
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 solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
/* https://leetcode.com/problems/word-pattern/ */ import java.util.HashMap; class WordPattern { public static void main(String args[]) { String pattern = "abba"; String str = "dog cat cat dog"; // String pattern = "abba"; String str = "dog cat cat fish"; // String pattern = "aaaa"; String str = "dog cat cat dog"; // String pattern = "abba"; String str = "dog dog dog dog"; WordPattern w = new WordPattern(); System.out.println(w.wordPattern(pattern, str)); } public boolean wordPattern(String pattern, String str) { if(str==null || pattern==null) false; String[] words = str.split("\\s"); if(pattern.length()!=words.length) return false; HashMap<Character, String> map1 = new HashMap<>(); HashMap<String, Character> map2 = new HashMap<>(); for(int i=0;i<pattern.length();i++) { System.out.println("i:"+i); if(map1.containsKey(pattern.charAt(i))) { if(!words[i].equals(map1.get(pattern.charAt(i)))) return false; } else { map1.put(pattern.charAt(i), words[i]); if(!map2.containsKey(words[i])) { map2.put(words[i], pattern.charAt(i)); } else return false; } } return true; } } |
Python solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
''' https://leetcode.com/problems/word-pattern/ ''' class Solution(object): def wordPattern(self, pattern, str): """ :type pattern: str :type str: str :rtype: bool """ dict = {} st = set() str = str.split() ln = len(str) if len(pattern) != ln: #print len(pattern), ln return False i = 0 for c in pattern: if str[i] in dict: if dict[str[i]] != c: return False else: if c in st: return False else: st.add(c) dict[str[i]] = c i += 1 return True |
#!/usr/bin/env python
# coding: utf-8
# # 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.
# In[2]:
#!/usr/bin/env python
# coding: utf-8
# function to check pattern and string
def check_str_pattern(pattern,str):
global str_list,pattern_list
str_list=str.split()
pattern_list=[i for i in pattern]
map_dict=zip(str_list,pattern_list)
len_check=check_length_str_pattern(str_list,pattern_list)
if len_check==True:
dict={j:i for i,j in map_dict}
print(dict)
new_list=[get_key(dict,i) for i in str_list]
print(“newlist:-“,new_list)
pt=””.join(new_list)
print(“Pt:-“,pt)
print(“Pattern:-“,pattern)
if pt in pattern:
print(“Both String and pattern constitue a similar shape”)
return True
else:
print(“But Both String and pattern donot constitue a similar shape”)
return False
else:
return False
# function to check length of string and pattern
def check_length_str_pattern(str_list,pattern_list):
if len(str_list)==len(pattern_list):
print(“Length for Pattern and string Check:- Passed”)
return True
else :
print(“Length for Pattern and string Check:- Failed”)
return False
# function to return key for any value
def get_key(dict,val):
for key, value in dict.items():
if val == value:
return key
return “NA”
# In[4]:Calling Parameters
pattern=input(“Input pattern to be matched :-“)
string=input(“Input String”)
print(“\n”)
check_str_pattern(pattern,string)
# In[4]:
pattern=input(“Input pattern to be matched :-“)
string=input(“Input String”)
print(“\n”)
check_str_pattern(pattern,string)