讯享网

题目:

给你一种规律  pattern  和一个字符串  str，请你判断  str  是否遵循其相同的规律。

这里我们指的是 完全遵循，例如 pattern  里的每个字母和字符串  str  中每个 非空 单词之间，存在着 双射 的对应规律。双射 意味着映射双方一一对应，不会存在两个字符映射到同一个字符串，也不会存在一个字符分别映射到两个不同的字符串。

示例:

1. 示例 1:

输入：pattern = "abab", s = "redblueredblue" 输出：true 解释：一种可能的映射如下： 'a' -> "red" 'b' -> "blue" 

2. 示例 2:

讯享网输入：pattern = "aaaa", s = "asdasdasdasd" 输出：true 解释：一种可能的映射如下： 'a' -> "asd" 

3. 示例 3:

输入：pattern = "abab", s = "asdasdasdasd" 输出：true 解释：一种可能的映射如下： 'a' -> "a" 'b' -> "sdasd" 注意 'a' 和 'b' 不能同时映射到 "asd"，因为这里的映射是一种双射。 

4. 示例 4:

讯享网输入：pattern = "aabb", s = "xyzabcxzyabc" 输出：false 

提示：

• 0 <= pattern.length <= 20
• 0 <= s.length <= 50
• pattern 和 s 由小写英文字母组成

抛砖引玉

相对于：单词规律 (难度:简单)本题失去了 s 中确定分割的单个元素，但是基于前面的逻辑：

• 声明两个 map 作为哈希表，来表达两个字符双向的映射关系
• 遇到映射关系冲突返回 false

pMs : pItem -> mapStr === sItem sMp : sItem -> mapPat === pItem 

其中 pItem 是单个模式字符，sItem 是从 s 中分割的字符串片段

那么逐个从 p 中取出元素（pItem）在 s 中尝试各种匹配组合：

• 如果 pItem 之前已经存在了映射字符串片段 sItem，那么校验枚举的字符片段是否与映射关系一致,
  如果之前的映射关系不一致，说明本轮枚举的 sItem 一定不满足继续枚举，如果满足，则递归匹配后续 pattern、s
• 如果 pItem 不存在映射字符串片段则在 pMs、sMp 分别添加映射关系

讯享网/ * @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 字符片段去尝试匹配，两个哈希表记录模式串与匹配串的映射关系

单从空间复杂度上看，其实每次校验是否冲突也是可以通过再次遍历哈希表完成：

• 从 pattern 中逐个截取元素与 s 片段匹配
• 如果之前哈希中存在本轮 pattern 选取的元素则交易是否相同（不相同继续枚举 s 片段，相同则切割 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) } 

博客: 前端小书童

公众号：前端小书童