描述
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.
分析
用一个 map 将 char 和 string 一一对应，如果 char 是第一次出现，建立一个对应关系，当然这里建立对应关系之前需要考察这个 string 是不是已经有 char 对应过了，怎么判断呢，还需要一个 set 集合，判断这个string在之前是否已经出现过了。如果 char 不是第一次出现了，那么就判断 map 中对应的 string 是否等于此时的 string。有意思的是c++中 string 是没有split方法的，所以用到了istringstream, 而java中有这个方法，和c++写的逻辑一样，java 要更coder friendly一点。
解决方案1(C++)
参考： https://leetcode.com/discuss/84973/sharing-my-c-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
| class Solution {
public:
bool wordPattern(string pattern, string str) {
map<char, string> char_str_map;
set<string> unique_string;
istringstream in(str);
int i = 0;
int pattern_size = pattern.size();
for(string word; in >> word; i++) {
if(char_str_map.find(pattern[i]) != char_str_map.end()) {
if(char_str_map[pattern[i]] != word) {
return false;
}
}else {
if(unique_string.find(word) != unique_string.end()) {
return false;
}
char_str_map[pattern[i]] = word;
unique_string.insert(word);
}
}
return i==pattern.size();
}
};
|
解决方案2(Java)
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
| public class Solution {
public boolean wordPattern(String pattern, String str) {
Map<Character, String> char_str_map = new HashMap<>();
Set<String> unique_string = new HashSet<>();
String[] strs = str.split(" ");
if(strs.length != pattern.length()) {
return false;
}
int i = 0;
for(; i < pattern.length(); i++) {
char c = pattern.charAt(i);
if(char_str_map.containsKey(c)) {
if(!char_str_map.get(c).equals(strs[i])) {
return false;
}
}else {
if(unique_string.contains(strs[i])) {
return false;
}
char_str_map.put(c, strs[i]);
unique_string.add(strs[i]);
}
}
return true;
}
}
|
相关问题
(H) Word Pattern II
(E) Isomorphic Strings