【一天一大 lee】单词规律 (难度:简单) - Day20201216
【一天一大 lee】单词规律 (难度:简单) - Day20201216
前端小书童
发布于 2021-01-05 10:08:43
发布于 2021-01-05 10:08:43
20201216
题目:
给定一种规律 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 包含了由单个空格分隔的小写字母。
抛砖引玉
有点像说出 AABC、AABB 模式成语的味道了...
看到题会觉得，恩，确实是简单的题，匹配每个模式字符的位置就好了，再仔细一想，恩? 不对，这 TM 是简单的题？
要怎么模式串转换成声明格式才能方便 s 去匹配呢，先想到的一定是哈希方法：
如果哈希记录每个模式字符的位置，但是缺少了模式字符与 s 中元素的对应关系，那么只能使用哈希记录模式串与 s 单个元素的对应关系，且对应关系是双向的。
- 声明两个哈希表
- 遍历 list&pattern,同时更新两个哈希表的映射关系
- 遇到映射关系冲突（pattern 某个字符对应 list 中元素，而 list 中元素不对应该字符）时返回 false
抛砖引玉
/**
* @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
}
使用 indexOf 标记映射
将每个元素第一次出现的位置作为元素的标记， 遍历 list&pattern：
- 如果模式字符和 s 的元素匹配，那么他们分别在 list 和 pattern 第一次出现的位置相同
- 如果他们不匹配（pattern 字符对应的 s 元素变化了），那么他们分别在 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 栏目 欢迎关注留言
公众号：前端小书童
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-12-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
