【LeetCode】查找和替换模式 Java 题解
题目描述
你有一个单词列表 words 和一个模式 pattern,你想知道 words 中的哪些单词与模式匹配。
如果存在字母的排列 p ,使得将模式中的每个字母 x 替换为 p(x) 之后,我们就得到了所需的单词,那么单词与模式是匹配的。
(回想一下,字母的排列是从字母到字母的双射:每个字母映射到另一个字母,没有两个字母映射到同一个字母。)
返回 words 中与给定模式匹配的单词列表。
你可以按任何顺序返回答案。
复制代码
思路分析
今天的算法题目是数组处理题目,题目要求判断 words 中哪些单词与模式匹配。我们判断模式是否匹配,就是找 pattern 的规律。
这个问题容易理解,思路很容易就想到了,接下来需要我们把思路转换成代码。两个模式相同,需要两者任一位置的字符都相同,我们定义一个 hashmap 来实现,记录 word 和 pattern 中单词的对应关系。若相等,则是一个答案。实现代码如下,供参考。
通过代码
复制代码
总结
上述算法的时间复杂度是 O(nm),空间复杂度是 O(n)
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/1e84e62918f99ca5acd56e97c】。文章转载请联系作者。
评论