leetCode-211:Design Add and Search Words Data Structure

问题描述

要求设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配。其中添加新单词时，新单词只包含小写字母。查找字符串时，字符串只包含 . 和小写字母，. 表示匹配任意一个字符。题目链接：**点我**

样例输入输出

输入：

[“WordDictionary”,”addWord”,”addWord”,”addWord”,”search”,”search”,”search”,”search”]
[[],[“bad”],[“dad”],[“mad”],[“pad”],[“bad”],[“.ad”],[“b..”]]

输出：

[null,null,null,null,false,true,true,true]

解释：

WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord(“bad”);
wordDictionary.addWord(“dad”);
wordDictionary.addWord(“mad”);
wordDictionary.search(“pad”); // return False
wordDictionary.search(“bad”); // return True
wordDictionary.search(“.ad”); // return True
wordDictionary.search(“b..”); // return True

输入：

[“WordDictionary”,”addWord”,”addWord”,”search”,”search”,”search”,”search”,”search”,”search”]
[[],[“a”],[“a”],[“.”],[“a”],[“aa”],[“a”],[“.a”],[“a.”]]

输出：

[null,null,null,true,true,false,true,false,false]

解释：

WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord(“a”);
wordDictionary.addWord(“a”);
wordDictionary.search(“.”); // return True
wordDictionary.search(“a”); // return True
wordDictionary.search(“aa”); // return False
wordDictionary.search(“a”); // return True
wordDictionary.search(“.a”); // return False
wordDictionary.search(“a.”); // return False

问题解法

使用前缀树，用单词的每个字母进行构造字典树。在查找时，判断当前字符是否是 . ，如果是，则判断是否存在字符，如果有则继续，否则返回 false。此过程最好使用递归。代码如下

class WordDictionary
{
    class Node
    {
        Node[] children = new Node[26];
        boolean isEnd = false;
        char ch;

        Node(char ch)
        {
            this.ch = ch;
        }
    }

    Node root;

    /** Initialize your data structure here. */
    public WordDictionary()
    {
        root = new Node('#');
    }

    public void addWord(String word)
    {
        Node current = root;
        for (char ch : word.toCharArray())
        {
            int index = ch - 'a';
            if (current.children[index] == null)
            {
                current.children[index] = new Node(ch);
            }

            current = current.children[index];
        }
        current.isEnd = true;
    }

    public boolean search(String word)
    {
        return search(word.toCharArray(), 0, root);
    }

    private boolean search(char[] words, int startIndex, Node startNode)
    {
        Node current = startNode;
        for (int i = startIndex; i < words.length; i++)
        {
            if (words[i] == '.')
            {
                for (int j = 0; j < 26; j++)
                {
                    if (current.children[j] != null)
                    {
                        boolean temp = search(words, i + 1, current.children[j]);
                        if (temp)
                        {
                            return true;
                        }
                    }
                }
                return false;
            }
            else
            {
                int index = words[i] - 'a';
                if (current.children[index] == null)
                {
                    return false;
                }

                current = current.children[index];
            }
        }

        return current.isEnd;
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */