这一题这么写对么？

面的一家大厂。后来hr说，这一轮coding，就是dictionary，先加一些词。然后，判断，有没有。一个dot表示一个字母，任意的。fo. 和foo是match的。我做的就是用trie写的。改写了search 成strongSearch。请各位看看。
   

class Trie {
    public TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
   
    public void insert(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            if (cur.branches[c-'a'] == null) {
                cur.branches[c-'a'] = new TrieNode();
            }
            cur = cur.branches[c-'a'];
        }
        cur.endWord = true;
    }

    public boolean strongSearch(TrieNode node, String word, int p) {
        if (node == null)
            return false;
        char c = word.charAt(p);
        if (c !='.') {
            if (node.branches[c-'a'] == null)
                return false;
            else {
                if(p == word.length()-1){
                    return node.branches[c-'a'].endWord;
                }
                return smartSearch(node.branches[c-'a'], word, p+1);
            }
        } else {
            for (int i = 0; i < 26; i++) {
                if(node.branches[i] != null) {
                    if(p == word.length()-1)
                        return node.branches[i].endWord;
                    if (smartSearch(node.branches[i], word, p+1))
                        return true;
                }
            }
        }
        return false;
    }
   
    public boolean search(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            if (cur.branches[c-'a'] == null) {
                return false;
            }
            cur = cur.branches[c-'a'];
        }
        return cur.endWord;
    }
   
    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (char c : prefix.toCharArray()) {
            if (cur.branches[c-'a'] == null) {
                return false;
            }
            cur = cur.branches[c-'a'];
        }
        return true;
    }
}

class TrieNode {
    public boolean endWord;
    public TrieNode[] branches;
    public TrieNode() {
        endWord = false;
        branches = new TrieNode[26];
    }

只是大概看了一下。我觉的对的 ，就是定义trie node, 然后插入是迭代，查找对wild card char进行递归。这是LC上的一个原题。

我感觉你在wild card查找递归时可以先判断index越界（单词结束）的情况，这样你在之后for loop调用时coding会简洁一些。
（其实任何递归函数都先处理边界情况作为关键的stop condition 保障）

zzgzzm 发表于 2020-8-15 02:19
只是大概看了一下。我觉的对的 ，就是定义trie node, 然后插入是迭代，查找对wild card char进行递归。这是 ...

我也觉得没写错。可是，feedback出来却说有很多bug。

zlove 发表于 2020-08-14 13:55:08
我也觉得没写错。可是，feedback出来却说有很多bug。

那你复制到LC 211测试一下吧。我觉的大体结构没问题，得看细节是否正确。

zzgzzm 发表于 2020-8-15 05:23
那你复制到LC 211测试一下吧。我觉的大体结构没问题，得看细节是否正确。

有个bug。心服口服