more-035
给你一种规律 pattern 和一个字符串 str,请你判断 str 是否遵循其相同的规律。
这里我们指的是 完全遵循,例如 pattern 里的每个字母和字符串 str 中每个 非空 单词之间,存在着 双射 的对应规律。双射 意味着映射双方一一对应,不会存在两个字符映射到同一个字符串,也不会存在一个字符分别映射到两个不同的字符串。
输入:pattern = "abab", s = "redblueredblue"
输出:true
解释:一种可能的映射如下:
'a' -> "red"
'b' -> "blue"
输入:pattern = "aaaa", s = "asdasdasdasd"
输出:true
解释:一种可能的映射如下:
'a' -> "asd"
输入:pattern = "abab", s = "asdasdasdasd"
输出:true
解释:一种可能的映射如下:
'a' -> "a"
'b' -> "sdasd"
注意 'a' 和 'b' 不能同时映射到 "asd",因为这里的映射是一种双射。
输入:pattern = "aabb", s = "xyzabcxzyabc"
输出:false
提示:
相对于20201216:单词规律 (难度:简单)本题失去了 s 中确定分割的单个元素,但是基于前面的逻辑:
pMs : pItem -> mapStr === sItem
sMp : sItem -> mapPat === pItem
其中 pItem 是单个模式字符,sItem 是从 s 中分割的字符串片段
那么逐个从 p 中取出元素(pItem)在 s 中尝试各种匹配组合:
抛砖引玉
/**
* @param {string} pattern
* @param {string} s
* @return {boolean}
*/
var wordPatternMatch = function(pattern, s) {
let pMs = new Map(),
sMp = new Map()
function helper(str, index, pMs, sMp) {
// 当p中元素取完且s也分割完则说明匹配成功
if (index >= pattern.length) {
if (str) return false
return true
}
const pItem = pattern[index],
mapStr = pMs.get(pItem)
for (let i = 1; i <= str.length; i++) {
const sItem = str.substring(0, i),
mapPat = sMp.get(sItem)
// s分割的片段不满足之前的映射关系,直接继续枚举sItem
if (
(pMs.has(pItem) && mapPat !== pItem) ||
(sMp.has(sItem) && mapStr !== sItem)
) {
continue
}
// 如果不存在p元素的映射则新增映射关系
if (!pMs.has(pItem)) {
pMs.set(pItem, sItem)
sMp.set(sItem, pItem)
}
// 递归后续匹配
if (helper(str.slice(i), index + 1, pMs, sMp)) return true
// 如果本轮枚举s片段时pItem映射的s片段为空,那么在每次枚举前都需要把映射关系重置回去
if (!mapStr) {
pMs.delete(pItem)
sMp.delete(sItem)
}
}
return false
}
// 特殊情况:都为空或者只有个为空
if (!pattern && !s) return true
if (!pattern || !s) return false
return helper(s, 0, pMs, sMp)
}
从上面解法可以看出来,本题的出题逻辑是从 pattern 中逐个选择元素然后分割 s 字符片段去尝试匹配,两个哈希表记录模式串与匹配串的映射关系
单从空间复杂度上看,其实每次校验是否冲突也是可以通过再次遍历哈希表完成:
var wordPatternMatch = function(pattern, s) {
let map = new Map()
function helper(pStr, sStr) {
// 匹配完成
if (pStr.length === 0) return sStr.length === 0
const pItem = pStr[0],
mapStr = map.get(pItem)
// 枚举s片段组合:pattern和s均切割则枚举时s边界发生变化
for (let i = 1; i <= sStr.length - pStr.length + 1; i++) {
const sItem = sStr.substring(0, i)
// 遇到已匹配映射或者找到全新映射
if (
(mapStr && sItem == mapStr) ||
(!mapStr && ![...map.values()].includes(sItem))
) {
map.set(pItem, sItem)
if (helper(pStr.substring(1), sStr.substring(i), map)) {
return true
} else if (!mapStr) {
map.delete(pItem)
}
}
}
return false
}
return helper(pattern, s)
}
博客: 前端小书童
每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言
公众号:前端小书童