[LeetCode] Word Pattern

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:

  1. pattern = "abba", str = "dog cat cat dog" should return true.
  2. pattern = "abba", str = "dog cat cat fish" should return false.
  3. pattern = "aaaa", str = "dog cat cat dog" should return false.
  4. pattern = "abba", str = "dog dog dog dog" should return false.

Notes:

  1. patterncontains only lowercase alphabetical letters, and str contains words separated by a single space. Each word in str contains only lowercase alphabetical letters.
  2. Both pattern and str do not have leading or trailing spaces.
  3. Each letter in pattern must 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 长度不对应,为空等。

 
 
上一篇:(String). Word Pattern


下一篇:BUG-FREE-For Dream