211. Add and Search Word - Data structure design

栏目: 数据库 · 发布时间: 5年前

内容简介:Design a data structure that supports the following two operations:void addWord(word)bool search(word)

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.

难度:medium

题目:

设计数据结构支持以下两操作:

void addWord(word)

bool search(word)

search(word) 可以查单词或包含.的正则表达式。 .可以表示任何单个字符。

注意:

你可以假定所有单词仅由小写字母组成。

思路:

Tire Tree, DFS

Runtime: 94 ms, faster than 89.57% of Java online submissions for Add and Search Word - Data structure design.

class WordDictionary {
    private TrieNode root;
    
    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new TrieNode();
    }
    
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        char c = word.charAt(0);
        int i = 0, idx = 0;
        TrieNode ptr = root;
        for (; i < word.length(); i++, ptr = ptr.next[idx]) {
            idx = word.charAt(i) - 'a';
            if (null == ptr.next[idx]) {
                ptr.next[idx] = new TrieNode();
            }
        }
        
        ptr.isWord = true;
    }
    
    // dfs 
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        return search(word, 0, root);
    }
    
    public boolean search(String word, int idx, TrieNode beginNode) {
        if (idx >= word.length() || null == beginNode) {
            return false;
        }
        
        TrieNode node = null;
        int c = word.charAt(idx), cIdx = c - 'a';
        if ('.' == c) {
            boolean result = false;
            for (int i = 0; i < 26; i++) {
                node = beginNode.next[i];
                if (null == node) {
                    continue;
                }
                if ((idx + 1) == word.length() && node.isWord) {
                    return true;   
                }
                result = result || search(word, idx + 1, beginNode.next[i]);
            }
            return result;
        }
        
        // c is not equal to '.'
        node = beginNode.next[cIdx];
        if (null == node) {
            return false;
        }
        if ((idx + 1) == word.length()) {
            return node.isWord;
        }
        
        return search(word, idx + 1, beginNode.next[cIdx]);
    }
    
    public static class TrieNode {
        public boolean isWord;
        public TrieNode[] next = new TrieNode[26];
    }
}

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

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

一本书读懂24种互联网思维

一本书读懂24种互联网思维

安杰 / 台海出版社 / 2015-3-1 / 39.80元

互联网思维已经不再局限于互联网,与当初人类史上的“文艺复兴”一样,这种思维的核心即将开始扩散开去,对整个大时代造成深远的影响。本书是深入研究互联网思维的精华之作,作者深入浅出地集中阐述了24种互联网思维的内核与精神,并结合实例对这24种互联网思维逐一进行了点评。对于个人与企业如何抓住互联网思维背后正喷薄而出的工作、生活、商业上的大革新与大机遇,如何在互联网思维下进行运作,如何运用互联网思维进行升级......一起来看看 《一本书读懂24种互联网思维》 这本书的介绍吧!

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试