Given apattern
and a stringstr
, find ifstr
follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter inpattern
and a non-empty word instr
.
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 assumepattern
contains only lowercase letters, andstr
contains lowercase letters separated by a single space.
Solution: pattern每种字母对应不同的单词。用hashmap记录对应关系,hashset记录已经出现过的单词
public boolean wordPattern(String pattern, String str) {
if (pattern == null || str == null || str.length() == 0) {
return false;
}
HashMap<Character, String> hashmap = new HashMap<>();
HashSet<String> hashset = new HashSet<>();
int j = 0, i = 0;
for (; i < pattern.length() && j < str.length(); i++) {
char c = pattern.charAt(i);
int k = j;
while(k < str.length() && str.charAt(k) != ' ') {
k++;
}
String substring = str.substring(j, k);
j = k + 1;
if (hashmap.containsKey(c)) {
if (!hashmap.get(c).equals(substring)) {
return false;
}
} else {
//看这单词是否已有字母对应
if (hashset.contains(substring)) {
return false;
}
hashmap.put(c, substring);
hashset.add(substring);
}
}
//要到末尾,避免有多余的字母或单词
return j == str.length() + 1 && i == pattern.length();
}