侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 26 条评论

目 录CONTENT

文章目录

【枚举】距离字典两次编辑以内的单词【力扣第 90 场双周赛】

GabrielxD
2022-10-30 / 0 评论 / 0 点赞 / 189 阅读 / 590 字
温馨提示:
本文最后更新于 2022-11-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

6228. 距离字典两次编辑以内的单词


给你两个字符串数组 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] 都只包含小写英文字母。

解题

方法一:枚举

思路

遍历 queries ,对于每一个 query 都与 dictionary 中所有字符串对比,如果可以在两次编辑内使两字符串相等,就把当前的 query 加入答案数组。

代码

class Solution {
    public List<String> twoEditWords(String[] queries, String[] dictionary) {
        int n = queries[0].length();
        List<char[]> dict = new ArrayList<>();
        for (String word : dictionary) dict.add(word.toCharArray());
        List<String> ans = new ArrayList<String>();
        for (String query : queries) {
            char[] curr = query.toCharArray();
            outer: for (char[] word : dict) {
                int diff = 0;
                for (int i = 0; i < n; ++i) {
                    if (word[i] != curr[i]) ++diff;
                    if (diff > 2) continue outer;
                }
                ans.add(query);
                break;
            }
        }
        return ans;
    }
}
0

评论区