Word Pattern
Total Accepted: 4627 Total Submissions: 17361 Difficulty: Easy
Given a pattern and a string str, find if str follows the same pattern.
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:
-
patterncontains only lowercase alphabetical letters, andstrcontains words separated by a single space. Each word instrcontains only lowercase alphabetical letters. - Both
patternandstrdo not have leading or trailing spaces. - Each letter in
patternmust map to a word with length that is at least 1.
Credits:
Special thanks to @minglotus6 for adding this problem and creating all test cases.
/**
* @param {string} pattern
* @param {string} str
* @return {boolean}
*/
var wordPattern = function(pattern, str) {
var s_to_p = {};
var p_to_s = {};
var pi = 0;
var si = 0;
if (!pattern || !str) return false;
while (pi < pattern.length) {
if (si >= str.length) return false;
var word = "";
var pt = pattern[pi];
while (si < str.length && str[si] != " ") {
word += str[si];
si++;
}
si++;
if (!s_to_p[word]) {
s_to_p[word] = pattern[pi];
}
else {
if (s_to_p[word] != pattern[pi]) return false;
} if (!p_to_s[pt]) {
p_to_s[pt] = word;
}
else {
if (p_to_s[pt] != word) return false;
}
pi++;
}
if (si < str.length) return false;
return true;
};
最简单的方法利用两个哈希表做双向的对应，主要容易错的是在各种edge cases，比如pattern 和 str 长度不对应，为空等。