Leetcode每日一题 —— 2452. 距离字典两次编辑以内的单词

2452. 距离字典两次编辑以内的单词 - 力扣（LeetCode）

2452. 距离字典两次编辑以内的单词 - 给你两个字符串数组 queries 和 dictionary 。数组中所有单词都只包含小写英文字母，且长度都相同。 一次 编辑 中，你可以从...

思路

输入规模不大，用暴力其实就能解决，而且还挺快的。

这题咱还觉着能用 Trie 树和回溯来做，思路也挺自然的。把字典中所有词加入树中后，对于查询中每个词，从根节点开始往下走，每一步最多有两个分支：

1. 使用一次编辑（注意，就算当前 Trie 结点有孩子能匹配，也要尝试用一次编辑，可能有 query=myword, dictionary=['mywayp', 'mvword'] 这种情况。
2. 不使用编辑，进入孩子结点（前提是有匹配的孩子）。

任意一个分支下能完全匹配查询时就不用继续了，避免重复加入结果。

实际跑起来这个思路好像确实没有暴力法快。

代码

struct TrieNode{
    bool exist;
    TrieNode* children[26];
    TrieNode(){
        exist=false;
        memset(children,0,sizeof(children));
    }
};

class Solution {
public:
    vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {
        // 此处的一次编辑只能变更一个字符，不能插入、删除字符
        // 这题的规模其实暴力也可以，字典树 + 回溯也可以试试

        TrieNode* root=new TrieNode();

        // 先把字典内容加入树中
        for(string& w:dictionary){
            TrieNode* ptr=root;
            for(int i=0;i<w.size();i++){
                if(ptr->children[w[i]-'a']==nullptr){
                    ptr->children[w[i]-'a']=new TrieNode();
                }
                ptr=ptr->children[w[i]-'a'];
            }
            ptr->exist=true;
        }

        vector<string> res;

        auto dfs=[&](auto&& self, const string& w,int i,TrieNode* ptr, int edit) -> bool {
            if(i>=w.size()){
                if(ptr->exist){
                    // 匹配上了
                    res.emplace_back(w);
                    return true;
                }
                return false;
            }

            int c=w[i]-'a';

            // 情况 1：不进行编辑，有相应的分支
            if(ptr->children[c]!=nullptr){
                if(self(self,w,i+1,ptr->children[c],edit)){
                    return true;
                }
            }

            // 情况 2：进行编辑
            if(edit>0){
                for(int j=0;j<26;j++){
                    if(j==c){
                        // 跳过当前字符，避免重复分支
                        continue;
                    }
                    if(ptr->children[j]!=nullptr&&self(self,w,i+1,ptr->children[j],edit-1)){
                        return true;
                    }
                }
            }

            // 情况 1 和情况 2 有一种分支让整个字符串匹配了就不用继续了

            return false;
        };

        // 对于每个查询进行处理
        for(string& q:queries){
            dfs(dfs, q, 0, root, 2);
        }
        return res;
    }
};

暴力解法：

class Solution {
public:
    vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {
        // 暴力法
        vector<string> res;
        for(string& q:queries){
            for(string& w:dictionary){
                if(q.size()!=w.size()){
                    // 长度不同直接 pass
                    continue;
                }
                // 逐个比较，最多两次替换
                int edit=2;
                for(int i=0;i<q.size();i++){
                    if(q[i]!=w[i]){
                        edit--;
                    }
                }
                if(edit>=0){
                    res.emplace_back(q);
                    break;
                }
            }
        }
        return res;
    }
};

1 个帖子 - 1 位参与者

阅读完整话题