X

LEETCODE 676. Implement Magic Dictionary 解题思路分析

题目大意:

实现一个魔法字典

实现一个带有buildDict, 以及 search方法的魔法字典。

对于buildDict方法,你将被给定一串不重复的单词来构建一个字典。

对于search方法,你将被给定一个单词,并且判定能否只将这个单词中一个字母换成另一个字母,使得所形成的新单词存在于你构建的字典中。

示例 1:

Input: buildDict(["hello", "leetcode"]), Output: Null
Input: search("hello"), Output: False
Input: search("hhllo"), Output: True
Input: search("hell"), Output: False
Input: search("leetcoded"), Output: False

注意:

  1. 你可以假设所有输入都是小写字母 a-z。
  2. 为了便于竞赛,测试所用的数据量很小。你可以在竞赛结束后,考虑更高效的算法。
  3. 请记住重置MagicDictionary类中声明的类变量,因为静态/类变量会在多个测试用例中保留。 请参阅这里了解更多详情。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=676

解题思路分析:

检查一个单词是否存在于一个字典之中,我们可以采用字典树Trie来解题。对于字典树,我们在之前的文章中曾提及过,如果你还没接触过这个概念,或者你对它还不太熟悉,强烈建议你去参考我之前对字典树的讲解:LEETCODE 1268. Search Suggestions System 解题思路分析。这会对你理解本题大有帮助。

本题与普通的字典树遍历有所不同,由于题目要求将单词替换一个字母后,再去查看字典树中是否存在,这需要我们在遍历时稍加改动。对于树形结构的遍历,dfs深度优先搜索是我们常用的方式,dfs递归中,我们查看当前节点的所有子节点,如果子节点为空跳过。如果子节点不为空,查看当前子节点是否是当前字母,如果相同,dfs递归至该子节点,如果dfs返回值为true,代表找到了一个合理单词,直接返回true。反之,我们可以将当前字符更改为该子节点,然后再递归至该子节点即可,同样,如果dfs返回值为true,直接返回true。注意路径中,我们只有一次更改的机会。递归的终止条件为:当遍历完字符串所有字符后,若当前节点是一个单词的结尾,并且我们使用了一次更改机会,那么说明我们找到了合理单词,返回true。反之返回false。

实现代码:

class Node{ // 字典树节点
    Node[] children = new Node[26]; // 26个子节点
    boolean isEndOfWord; // 当前节点是否为单词结尾
}
Node root; // 根节点
/** Initialize your data structure here. */public MagicDictionary() {
    root=new Node();
}

/** Build a dictionary through a list of words */public void buildDict(String[] dict) {
    for(String d : dict){ // 将每个单词加入字典树
        add(d);
    }
}

void add(String s){
    Node r = root; // 当前根节点
    char[] arr=s.toCharArray(); // 为了提高效率,将字符串转为字符数组
    for(int i=0;i<arr.length;i++){ // 循环每一个字符
        int c=arr[i]-'a'; // 当前字符的下标
        if(r.children[c]==null){ // 如果当前子节点为空
            r.children[c]=new Node(); // 新建该子节点
        }
        r=r.children[c]; // 将根节点设置为当前子节点
    }
    r.isEndOfWord=true; // 最后一个字符所在节点为true
}

/** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */public boolean search(String word) {
    return dfs(root,word.toCharArray(),0,0); // dfs查看是否存在
}

boolean dfs(Node node, char[] arr, int index, int modifyCount){
    if(index==arr.length){ // 递归结束条件,遍历完单词每个字符
        // 如果当前节点为一个单词的结束位置,并且使用了一次修改,返回true
        if(node.isEndOfWord && modifyCount==1) return true;
        return false; // 返回false
    }
    int c = arr[index]-'a'; // 当前字符
    for(int i=0;i<26;i++){ // 循环26个子节点
        if(node.children[i]!=null){ // 子节点不为空
            if(i==c){ // 该子节点为当前字符
                // dfs递归至该子节点,修改次数不变,下标加一
                if(dfs(node.children[i],arr,index+1,modifyCount)){
                    return true; // 递归返回结果为true,返回true。
                }
            }else if(modifyCount==0){ // 该子节点不是当前字符,并且还有修改次数
                // dfs递归至该子节点,修改次数加一,下标加一
                if(dfs(node.children[i],arr,index+1,modifyCount+1)){
                    return true; // 递归返回结果为true,返回true。。
                }
            }
        }
    }
    return false;
}

本题解法执行时间为9ms。

Runtime: 9 ms, faster than 98.41% of Java online submissions for Implement Magic Dictionary.

Memory Usage: 38.3 MB, less than 62.06% of Java online submissions for Implement Magic Dictionary.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-676-implement-magic-dictionary-解题思路分析/
Categories: leetcode
kwantong: