LeetCode题目笔记——6228. 距离字典两次编辑以内的单词

43 阅读 0 评论 29 点赞

我是靠谱客的博主谨慎钢笔，最近开发中收集的这篇文章主要介绍LeetCode题目笔记——6228. 距离字典两次编辑以内的单词，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

文章目录

- 题目描述
- 题目难度——中等
- 方法一：模拟
- - 代码/Python
  - 代码/C++
- 总结

题目描述

这个题目也是昨晚周赛的题目，是第二题

给你两个字符串数组 queries 和 dictionary 。数组中所有单词都只包含小写英文字母，且长度都相同。

一次编辑中，你可以从 queries 中选择一个单词，将任意一个字母修改成任何其他字母。从 queries 中找到所有满足以下条件的字符串：不超过 两次编辑内，字符串与 dictionary 中某个字符串相同。

请你返回 queries 中的单词列表，这些单词距离 dictionary 中的单词编辑次数 不超过 两次。单词返回的顺序需要与 queries 中原本顺序相同。

示例1：

输入：queries = [“word”,“note”,“ants”,“wood”], dictionary = [“wood”,“joke”,“moat”]
输出：[“word”,“note”,“wood”]
解释：

将 “word” 中的 ‘r’ 换成 ‘o’ ，得到 dictionary 中的单词 “wood” 。
将 “note” 中的 ‘n’ 换成 ‘j’ 且将 ‘t’ 换成 ‘k’ ，得到 “joke” 。
“ants” 需要超过 2 次编辑才能得到 dictionary 中的单词。
“wood” 不需要修改（0 次编辑），就得到 dictionary 中相同的单词。所以我们返回 [“word”,“note”,“wood”] 。

示例2：

输入：queries = [“yes”], dictionary = [“not”]
输出：[]
解释：
“yes” 需要超过 2 次编辑才能得到 “not” 。
所以我们返回空数组。

提示：

1 <= queries.length, dictionary.length <= 100
n == queries[i].length == dictionary[j].length
1 <= n <= 100
所有 queries[i] 和 dictionary[j] 都只包含小写英文字母。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/words-within-two-edits-of-dictionary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目难度——中等

方法一：模拟

题目保证了输入每次输入的两个数组里每个字符串都是一样长的，所以我们可以直接利用这一点。每次编辑的条件是替换一个字母变成dictionary数组里的字符串，换句话说就变成了数一下queries里的字符串和dictionary里的字符串对应位置不一样的数量，比如word和wood，只有第三位r和o不一样，就可以编辑，而word和joke，就有3位都不一样，就不可以编辑。因此我们只需要遍历两个数组，让他们两两配对，数一下有几个位置不一样，超过两个的就不可以编辑。

代码/Python

class Solution:
    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
        res = []
        for qur in queries:
            n = len(qur)
            for dic in dictionary:
                count_dif = 0
                for i in range(n):
                    if qur[i] != dic[i]:
                        count_dif += 1
                
                if count_dif <= 2:
                    res.append(qur)
                    break
        
        return res

在这里插入图片描述
需要注意的是在内层循环时找到满足条件的字符串之后需要跳出内层循环，否则当dictionary里面有多个字符串能满足条件时，会有相同的多个qur被加入结果，即答案重复。跳出循环也能节约一点时间，倘若不想跳出，还可以把res用集合set来替代。

代码/C++

class Solution {
public:
    vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {
        vector<string> res;
        int count_dif = 0, i;
        for(auto qur: queries){
            for(auto dic: dictionary){
                count_dif = 0;
                for(i = 0; i < qur.size(); i++){
                    if(qur[i] != dic[i]){
                        ++count_dif;
                    }
                }
                if(count_dif <= 2){
                    res.push_back(qur);
                    break;
                }
            }
        }
        return res;
    }
};