Related: LeetCode 291 Word Pattern II
[LeetCode]Word Pattern | 书影博客
http://blog.csdn.net/xudli/article/details/48932055
X. 2 Hashmaps
http://buttercola.blogspot.com/2015/10/leetcode-word-pattern.html
The problem can be solved by using hash map. Note that some edge cases must be considered:
1. It must be a one-one mapping. e.g.
"abba", "dog dog dog dog" => false, since a and b maps to the dog.
"aaaa", "dog cat cat dog" => false, since a maps to both dog and cat.
So we may use two hash tables to maintain such a one-one mapping relationship. Note that in Java we may use map.containsValue().
2. The length of the pattern and number of tokens in the str must be the same. Otherwise, return false;
http://shibaili.blogspot.com/2015/10/day-132-287-find-duplicate-number.html
2个hashmap 互相对应
X. http://my.oschina.net/Tsybius2014/blog/514983
Not really better.
X.
Not efficient. As hashMap.containsValue is o(n).
http://my.oschina.net/Tsybius2014/blog/514983
X. Two HashMap
http://www.cnblogs.com/jcliBlogger/p/4857854.html
http://yuancrackcode.com/2015/11/27/word-pattern/
Find all strings that match specific pattern in a dictionary - GeeksforGeeks
Given a dictionary of words, find all strings that matches the given pattern where every character in the pattern is uniquely mapped to a character in the dictionary.
Read full article from [LeetCode]Word Pattern | 书影博客
[LeetCode]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
https://discuss.leetcode.com/topic/26339/8-lines-simple-javaYou may assume
pattern
contains only lowercase letters, and str
contains lowercase letters separated by a single space.public boolean wordPattern(String pattern, String str) {
String[] words = str.split(" ");
if (words.length != pattern.length())
return false;
Map index = new HashMap();
for (Integer i=0; i<words.length; ++i)
if (index.put(pattern.charAt(i), i) != index.put(words[i], i))
return false;
return true;
}
I go through the pattern letters and words in parallel and compare the indexes where they last appeared.
Edit 1: Originally I compared the first indexes where they appeared, using
putIfAbsent
instead of put
. That was based on mathsam's solution for the old Isomorphic Strings problem. But then czonzhu's answer below made me realize that put
works as well and why.
Edit 2: Switched from
for (int i=0; i<words.length; ++i)
if (!Objects.equals(index.put(pattern.charAt(i), i),
index.put(words[i], i)))
return false;
to the current version with
i
being an Integer
object, which allows to compare with just !=
because there's no autoboxing-same-value-to-different-objects-problem anymore. Thanks to lap_218 for somewhat pointing that out in the comments.
使用字典dict分别记录pattern到word的映射以及word到pattern的映射
这道题和题目Isomorphic Strings十分类似
http://segmentfault.com/a/1190000003827151
def wordPattern(self, pattern, str):
words = str.split()
if len(pattern) != len(words):
return False
ptnDict, wordDict = {}, {}
for ptn, word in zip(pattern, words):
if ptn not in ptnDict:
ptnDict[ptn] = word
if word not in wordDict:
wordDict[word] = ptn
if wordDict[word] != ptn or ptnDict[ptn] != word:
return False
return Truehttp://segmentfault.com/a/1190000003827151
public boolean wordPattern(String pattern, String str) {
Map<Character, String> map = new HashMap<Character, String>();
Set<String> set = new HashSet<String>();
String[] pieces = str.split(" ");
if(pieces.length != pattern.length()) return false;
int i = 0;
for(String s : pieces){
char p = pattern.charAt(i);
System.out.println(p);
// 如果该字符产生过映射
if(map.containsKey(p)){
// 且映射的字符串和当前字符串不一样
if(!s.equals(map.get(p))) return false;
} else {
// 如果该字符没有产生过映射
// 如果当前字符串已经被映射过了
if(set.contains(s)) return false;
// 否则新加一组映射
map.put(p, s);
set.add(s);
}
i++;
}
return true;
}
http://blog.csdn.net/xudli/article/details/48932055
- public boolean wordPattern(String pattern, String str) {
- //input check
- String[] strs = str.split(" ");
- if(pattern.length() != strs.length ) return false;
- Map<Character, String> map = new HashMap<>();
- Set<String> unique = new HashSet<>();
- for(int i=0; i<pattern.length(); i++) {
- char c = pattern.charAt(i);
- if(map.containsKey(c) ) {
- if(!map.get(c).equals(strs[i])) return false;
- } else {
- if(unique.contains(strs[i])) return false;
- map.put(c, strs[i]);
- unique.add(strs[i]);
- }
- }
- return true;
- }
X. 2 Hashmaps
http://buttercola.blogspot.com/2015/10/leetcode-word-pattern.html
The problem can be solved by using hash map. Note that some edge cases must be considered:
1. It must be a one-one mapping. e.g.
"abba", "dog dog dog dog" => false, since a and b maps to the dog.
"aaaa", "dog cat cat dog" => false, since a maps to both dog and cat.
So we may use two hash tables to maintain such a one-one mapping relationship. Note that in Java we may use map.containsValue().
2. The length of the pattern and number of tokens in the str must be the same. Otherwise, return false;
public
boolean
wordPattern(String pattern, String str) {
if
(pattern ==
null
|| pattern.length() ==
0
|| str ==
null
|| str.length() ==
0
) {
return
false
;
}
String[] tokens = str.split(
" "
);
if
(pattern.length() != tokens.length) {
return
false
;
}
Map<String, Character> inverseMap =
new
HashMap<>();
Map<Character, String> map =
new
HashMap();
int
i =
0
;
for
(i =
0
; i < pattern.length(); i++) {
char
digit = pattern.charAt(i);
String token = tokens[i];
// Check the one-one mapping
if
(!map.containsKey(digit) && !inverseMap.containsKey(token)) {
map.put(digit, token);
inverseMap.put(token, digit);
}
else
if
(map.containsKey(digit) && inverseMap.containsKey(token)) {
String token1 = map.get(digit);
char
digit1 = inverseMap.get(token);
if
(!token1.equals(token) || digit != digit1) {
return
false
;
}
}
else
{
return
false
;
}
}
return
true
;
}
}
2个hashmap 互相对应
string getWord(string str,
int
&index) {
string rt =
""
;
for
(; index < str.length(); index++) {
if
(
isalpha
(str[index])) {
rt += str[index];
}
else
break
;
}
index++;
return
rt;
}
bool
wordPattern(string pattern, string str) {
unordered_map<
char
,string> pToS;
unordered_map<string,
char
> sToP;
int
index = 0;
for
(
int
i = 0; i < pattern.length(); i++) {
if
(index == str.length())
return
false
;
string word = getWord(str,index);
if
(pToS.find(pattern[i]) == pToS.end()) {
pToS[pattern[i]] = word;
}
else
if
(word != pToS[pattern[i]])
return
false
;
if
(sToP.find(word) == sToP.end()) {
sToP[word] = pattern[i];
}
else
if
(sToP[word] != pattern[i])
return
false
;
}
return
index == str.length() + 1;
}
Not really better.
另一个办法需要利用HashMap中put函数的性质。
put函数的声明如下:
1
| public V put(K key, V value) |
它的功能是将键值对存入map中,如果map中原本就包含要插入的键,将旧值替换为新值。对于该函数的返回值,如果要插入的键在字典中不存在,则返回null,否则返回替换前的值。
public
boolean
wordPattern(String pattern, String str) {
if
(pattern.isEmpty() || str.isEmpty()) {
return
false
;
}
String[] s = str.split(
" "
);
if
(s.length != pattern.length()) {
return
false
;
}
@SuppressWarnings
(
"rawtypes"
)
HashMap<Comparable, Integer> hashMap =
new
HashMap<Comparable, Integer>();
for
(
int
i =
0
; i < pattern.length(); i++) {
if
(!Objects.equals(hashMap.put(pattern.charAt(i), i), hashMap.put(s[i], i)))
return
false
;
}
return
true
;
}
Not efficient. As hashMap.containsValue is o(n).
http://my.oschina.net/Tsybius2014/blog/514983
public
boolean wordPattern(String pattern, String str) {
if
(pattern.isEmpty() || str.isEmpty()) {
return
false
;
}
String[] s = str.split(
" "
);
if
(s.length != pattern.length()) {
return
false
;
}
HashMap<Character, String> hashMap =
new
HashMap<Character, String>();
for
(
int
i = 0; i < pattern.length(); i++) {
if
(hashMap.containsKey(pattern.charAt(i))) {
if
(!hashMap.
get
(pattern.charAt(i)).
equals
(s[i])) {
return
false
;
}
}
else
if
(hashMap.containsValue(s[i])) {
return
false
;
}
else
{
hashMap.put(pattern.charAt(i), s[i]);
}
}
return
true
;
}
http://www.cnblogs.com/jcliBlogger/p/4857854.html
3 bool wordPattern(string pattern, string str) { 4 unordered_map<char, int> p2i; 5 unordered_map<string, int> w2i; 6 istringstream in(str); 7 int i = 0, n = pattern.length(); 8 for (string word; in >> word; i++) { 9 if (i >= n || p2i[pattern[i]] != w2i[word]) 10 return false; 11 p2i[pattern[i]] = w2i[word] = i + 1; 12 } 13 return i == n; 14 }X. http://likemyblogger.blogspot.com/2015/10/leetcode-290-word-pattern.html
bool wordPattern(string pattern, string str) {
unordered_map<char, string> hash1;
unordered_map<string, char> hash2;
int np = pattern.size();
int l = 0, r, sz = str.size();
for
(int i=0; i<np; ++i){
if
(l>=sz)
return
false
;
//number of words < np
r = l;
while
(r<sz && str[r]!=
' '
) r++;
string word = str.substr(l, r-l);
l = r+1;
char c = pattern[i];
if
(hash1.count(c)==0){
hash1[c] = word;
}
else
if
(hash1[c]!=word){
return
false
;
}
if
(hash2.count(word)==0){
hash2[word] = c;
}
else
if
(hash2[word]!=c){
return
false
;
}
}
return
r==sz;
}
Find all strings that match specific pattern in a dictionary - GeeksforGeeks
Given a dictionary of words, find all strings that matches the given pattern where every character in the pattern is uniquely mapped to a character in the dictionary.
dict = ["abb", "abc", "xyz", "xyy"]; pattern = "foo" Output: [xyy abb] Explanation: xyy and abb have same character at index 1 and 2 like the pattern
The idea is to encode the pattern in such a way that any word from the dictionary that matches the pattern will have same hash as that of the pattern after encoding. We iterate through all words in dictionary one by one and print the words that have same hash as that of the pattern.
// Function to encode given string
string encodeString(string str)
{
unordered_map<
char
,
int
> map;
string res =
""
;
int
i = 0;
// for each character in given string
for
(
char
ch : str)
{
// If the character is occurring for the first
// time, assign next unique number to that char
if
(map.find(ch) == map.end())
map[ch] = i++;
// append the number associated with current
// character into the output string
res += to_string(map[ch]);
}
return
res;
}
// Function to print all the strings that match the
// given pattern where every character in the pattern is
// uniquely mapped to a character in the dictionary
void
findMatchedWords(unordered_set<string> dict,
string pattern)
{
// len is length of the pattern
int
len = pattern.length();
// encode the string
string hash = encodeString(pattern);
// for each word in the dictionary
for
(string word : dict)
{
// If size of pattern is same as size of current
// dictionary word and both pattern and the word
// has same hash, print the word
if
(word.length() == len && encodeString(word) == hash)
cout << word <<
" "
;
}
}