20201216
给定一种规律 pattern 和一个字符串 str ,判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配,例如, pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
输入: pattern = "abba", str = "dog cat cat dog"
输出: true
输入:pattern = "abba", str = "dog cat cat fish"
输出: false
输入: pattern = "aaaa", str = "dog cat cat dog"
输出: false
输入: pattern = "abba", str = "dog dog dog dog"
输出: false
说明:
有点像说出 AABC、AABB 模式成语的味道了...
看到题会觉得,恩,确实是简单的题,匹配每个模式字符的位置就好了,再仔细一想,恩? 不对,这 TM 是简单的题?
要怎么模式串转换成声明格式才能方便 s 去匹配呢,先想到的一定是哈希方法:
如果哈希记录每个模式字符的位置,但是缺少了模式字符与 s 中元素的对应关系,那么只能使用哈希记录模式串与 s 单个元素的对应关系,且对应关系是双向的。
抛砖引玉
/**
* @param {string} pattern
* @param {string} s
* @return {boolean}
*/
var wordPattern = function(pattern, s) {
const list = s.split(' ')
// 长度不匹配
if (list.length !== pattern.length) return false
let pMs = new Map(),
sMp = new Map(),
index = 0
while (index < list.length) {
const pStr = pattern[index],
sStr = list[index]
// 双向对应关系冲突
if (
(pMs.has(pStr) && pMs.get(pStr) !== sStr) ||
(sMp.has(sStr) && sMp.get(sStr) !== pStr)
) {
return false
}
pMs.set(pStr, sStr)
sMp.set(sStr, pStr)
index++
}
return true
}
将每个元素第一次出现的位置作为元素的标记, 遍历 list&pattern:
var wordPattern = function(pattern, s) {
const list = s.split(' ')
// 长度不匹配
if (list.length !== pattern.length) return false
let index = 0
while (index < list.length) {
const pStr = pattern[index],
sStr = list[index]
if (pattern.indexOf(pStr) != list.indexOf(sStr)) return false
index++
}
return true
}
博客: 前端小书童
每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言
公众号:前端小书童