[LeetCode] 211. Add and Search Word - Data structu

mozillazg 发布于2019-08-16 13:28 / 1077人阅读

Problem

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z.

Solution

class WordDictionary {
    public class TrieNode {
        public TrieNode[] children = new TrieNode[26];
        public boolean isWord = false;
    }
    
    TrieNode root = new TrieNode();
    
    public void addWord(String word) {
        TrieNode node = root;
        for (char ch: word.toCharArray()) {
            if (node.children[ch-"a"] == null) {
                node.children[ch-"a"] = new TrieNode();
            }
            node = node.children[ch-"a"];
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        return helper(word, 0, root);
    }
    
    private boolean helper(String word, int start, TrieNode node) {
        if (start == word.length()) return node.isWord;
        char ch = word.charAt(start);
        if (ch == ".") {
            for (int i = 0; i < 26; i++) {
                if (node.children[i] != null && helper(word, start+1, node.children[i])) {
                    return true;
                }
            }
        } else {
            return node.children[ch-"a"] != null && helper(word, start+1, node.children[ch-"a"]);
        }
        return false;
    }
}

海外云主机服务器托管 Data_ADD L211 LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71804.html

leetcode-211-Add and Search Word - Data structure

摘要：原题总结栈的利用，先进后出的作用，可以保持链表一类的数据的连贯操作，可以用来替代广度搜索。每一层次可以用进栈出栈进行替代。形式的数据结构，有记忆状态的作用。应用字符串的遍历，广度搜索。原题： 211. Add and Search Word - Data structure design Design a data structure that supports the follo...

Alliot 2019-07-30 17:34 评论0 收藏0
[LeetCode] 642. Design Search Autocomplete System

Problem Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character #). For each character they type except #, you need to r...

MartinHan 2019-08-16 13:40 评论0 收藏0
[LeetCode] 212. Word Search II

Problem Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cell, where adjacent cells are those ...

Flands 2019-08-16 13:40 评论0 收藏0
[Leetcode] Word Search 单词搜索

摘要：我们可以先用待查单词建立一个字典树，这样我们在从矩阵中某个点开始深度优先搜索时，可以直接用字典树判断当前组成的字符串是否是某个单词的前缀。字典树同样也提供接口，所以同样可以用于判断是否已经搜索到这个词了。 Word Search I 更新的思路与解法请访问：https://yanjia.me/zh/2018/11/... Given a 2D board and a word, f...

objc94 2019-08-14 12:25 评论0 收藏0
[Leetcode] Implement Trie 实现前缀树

摘要：压缩前缀树其实就是将所有只有一个子节点的节点合并成一个，以减少没有意义的类似链表式的链接。然后我们开始遍历这个前缀树。 Implement Trie Implement a trie with insert, search, and startsWith methods. Note: You may assume that all inputs are consist of lowe...

jsliang 2019-08-14 12:28 评论0 收藏0