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.
解题思路
- 用一个哈希表建立从pattern中字符到str中字符串的映射。
- 用一个集合表示str中字符串是否已作为值出现在哈希表中。
以下两种情况为假:
- 哈希表中已存在key,但是对应的value值不一样。
- 哈希表中不存在key,但是对应的值已作为其他key的value值。
实现代码
C++:
// Runtime: 0 ms
class Solution {
public:
bool wordPattern(string pattern, string str) {
vector<string> words;
istringstream iss(str);
string temp;
while (iss>>temp)
{
words.push_back(temp);
}
if (words.size() != pattern.size())
{
return false;
}
unordered_map<char, string> mymap;
set<string> used;
for (int i = 0; i < pattern.length(); i++)
{
if (mymap.find(pattern[i]) == mymap.end())
{
if (used.find(words[i]) == used.end())
{
mymap[pattern[i]] = words[i];
used.insert(words[i]);
}
else
{
return false;
}
}
else if (mymap[pattern[i]].compare(words[i]) != 0)
{
return false;
}
}
return true;
}
};
Java:
// Runtime: 3 ms
public class Solution {
public boolean wordPattern(String pattern, String str) {
String words[] = str.split(" ");
if (pattern.length() != words.length) {
return false;
}
Map<Character, String> mymap = new HashMap<Character, String>();
for (int i = 0; i < pattern.length(); i++) {
if (!mymap.containsKey(pattern.charAt(i))) {
if (!mymap.containsValue(words[i])) {
mymap.put(pattern.charAt(i), words[i]);
}
else {
return false;
}
}
else if (!mymap.get(pattern.charAt(i)).equals(words[i])) {
return false;
}
}
return true;
}
}