专栏首页木又AI帮【leetcode刷题】T95-查找和替换模式

【leetcode刷题】T95-查找和替换模式

【题目】

你有一个单词列表 words 和一个模式  pattern,你想知道 words 中的哪些单词与模式匹配。

如果存在字母的排列 p ,使得将模式中的每个字母 x 替换为 p(x) 之后,我们就得到了所需的单词,那么单词与模式是匹配的。

(回想一下,字母的排列是从字母到字母的双射:每个字母映射到另一个字母,没有两个字母映射到同一个字母。)

返回 words 中与给定模式匹配的单词列表。

你可以按任何顺序返回答案。

示例:

输入:words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
输出:["mee","aqq"]
解释:
"mee" 与模式匹配,因为存在排列 {a -> m, b -> e, ...}。
"ccc" 与模式不匹配,因为 {a -> c, b -> c, ...} 不是排列。
因为 a 和 b 映射到同一个字母。

提示:

1 <= words.length <= 50 1 <= pattern.length = words[i].length <= 20

【思路】

使用两个字典/map,保证单词和pattern的字符一一对应。

【代码】

python版本

class Solution(object):
    def findAndReplacePattern(self, words, pattern):
        """
        :type words: List[str]
        :type pattern: str
        :rtype: List[str]
        """
        res = []
        for word in words:
            # 长度不同,肯定不满足
            if len(word) != len(pattern):
                continue
            d1 = {}
            d2 = {}
            i = 
            # 模式相同
            while i < len(pattern):
                p = pattern[i]
                if p not in d1:
                    d1[p] = word[i]
                elif d1[p] != word[i]:
                    break
                if word[i] not in d2:
                    d2[word[i]] = p
                elif d2[word[i]] != p:
                    break
                i += 
            if i == len(pattern):
                res.append(word)
        return res

C++版本

class Solution {
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        map<char, char> d1;
        map<char, char> d2;
        vector<string> res;
        for(auto word: words){
            // 长度不同,不满足
            if(word.size() != pattern.size())
                continue;
            // 清空
            d1.clear();
            d2.clear();
            int i = ;
            for(i=; i<pattern.size(); i++){
                if(d1.find(word[i]) == d1.end())
                    d1[word[i]] = pattern[i];
                else
                    if(d1[word[i]] != pattern[i])
                        break;
                if(d2.find(pattern[i]) == d2.end())
                    d2[pattern[i]] = word[i];
                else
                    if(d2[pattern[i]] != word[i])
                        break;
            }
            if(i == pattern.size())
                res.push_back(word);
        }
        return res;
    }
};

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode刷题】T210-最大交换

    https://leetcode-cn.com/problems/maximum-swap/

    木又AI帮
  • 【leetcode刷题】T74-字符串相加

    为了避免这种情况,我们保持num1长度较大(如果num2长度较大,则和num1互换),前一个过程的累加a+b+flag,累加次数为num2.size()这么多次...

    木又AI帮
  • 【leetcode刷题】T91-旋转数字

    我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后,我们仍可以得到一个有效的,且和 X 不同的数。要求每位数字都要被旋转。

    木又AI帮
  • 从零开始搭建Java开发环境第一篇:Java工程师必备软件大合集

    https://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151....

    黄小斜
  • Java工程师必备软件大合集,手把手教你如何下载和安装

    https://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151....

    Java技术江湖
  • 生物医学领域科研工作者的软件和工具清单-3.0版本

    微软的Office和金山的WPS,大家不陌生,应该都有。WPS免费,Office需要破解,这里提供破解版下载地址:

    DoubleHelix
  • 6月机器学习热文TOP10,精选自1400篇文章

    每月一次的热文推荐又来了!这次,我们从将近 1400 篇机器学习文章中挑出了 10 篇热文,以飨读者。

    IT派
  • 一文教你提高算法和数据结构技能

    ? 如果你想在算法和数据结构上做得更好,你首先需要做的就是建立一个坚实的基础。这个基础可以通过多种方式学习,通过大学的计算机科学课程,或者参加一些编程训练营,...

    AiTechYun
  • ObjectDataSource选择业务对象列表为空的探讨

    前天晚上,在一个页面上拖了一个ObjectDataSource,配置数据源时发现选择业务对象的列表没有列出当前项目的实体类,甚至连NewLife.CommonE...

    大石头
  • 网站定位之---根据IP获得区域

    记得以前做一个培训机构网站时候需要定位,那时候用的搜狐的api,不是很精准。 后来做电商的时候用的新浪的api,感觉还行,,,,,当时就想要是有本地ip库多爽啊...

    逸鹏

扫码关注云+社区

领取腾讯云代金券