LeetCode笔记：单词规律
问题
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
示例 1:
输入: pattern =
"abba", str ="dog cat cat dog"输出: true
示例 2:
输入: pattern =
"abba", str ="dog cat cat fish"输出: false
示例 3:
输入: pattern =
"aaaa", str ="dog cat cat dog"输出: false
示例 4:
输入: pattern =
"abba", str ="dog dog dog dog"输出: false
说明:
你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。
解法
思路：
一般思路是把字符串切分成数组，然后再遍历处理，我们这里用一个新的方法-正则表达式。
- 因为字符串
s是空格分隔的英文单词，很有规律性，可以用正则表达式解析s字符串，匹配到每一个单独的单词。在replace方法的回调函数里，处理每一个单词。 - 我们构造一个 map，用于记录每一个单词和对应位置的
pattern字母。我们给单词加一个前缀，防止pattern字母冲突，因为单词也可能是一个字母。 - 每处理一个单词，我们都需要判断如果已经出现过这个单词或者
pattern字母，当前的对应值是否和上次出现的一致，一旦出现不一致，即没有遵循规律。这里需要同时判断单词和pattern字母以保证真正的双向连接。 - 最后处理一个特殊情况，如果只有一个单词的情况下，因为没有足够的对比，我们的
replace回调函数内部无法发现问题，所以在最后判断一下确保s和pattern的长度需要保持相同。
代码：
/**
* @param {string} pattern
* @param {string} s
* @return {boolean}
*/
var wordPattern = function (pattern, s) {
var count = 0;
var map = new Map();
var flag = true;
var rr = s.replace(/\b(?=\S)(\S*)/g, function ($0) {
// 跟随s的replace匹配得到对应的pattern字母
let p = pattern[count++];
// 用于返回值
let r = p + $0;
// 1. p 和 "$" + $0 都需要判断
// get(p) : 'aaaa':'dog cat cat dog'
// get('$' + $0) : 'abba':'dog dog dog dog'
// 2. 加一个前缀 '$' + $0，解决 'abc':'c b a'
if (
(map.has(p) && map.get(p) !== $0) ||
(map.has("$" + $0) && map.get("$" + $0) !== p)
) {
flag = false;
} else {
map.set(p, $0);
map.set("$" + $0, p);
}
return r;
});
// 3. pattern的长度必须等于s的长度, 解决 'jquery':'jquery'
return flag && rr.split(" ").length === pattern.length;
};
评论