Alibi

My Life is Getting Better

Leetcode[211]Add and Search Word - Data structure design

18 Nov 2015

###Task1 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.

For 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.

###Python ####O(n)

class TrieNode(object):
    def __init__(self):
        self.children = [None for i in range(26)]
        self.saved = False
class WordDictionary(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.root = TrieNode()
        

    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: void
        """
        cur = self.root
        for ch in word:
            if not cur.children[ord(ch) - ord('a')]:
                cur.children[ord(ch) - ord('a')] = TrieNode()
            cur = cur.children[ord(ch) - ord('a')]
        cur.saved = True

    def search(self, word):
        """
        Returns if the word is in the data structure. A word could
        contain the dot character '.' to represent any one letter.
        :type word: str
        :rtype: bool
        """
        cur = self.root
        return self.dfs(cur, word)
    def dfs(self, cur, word):
        if not cur:
            return False
        if len(word) == 0:
            return cur.saved
        if word[0] == '.':
            for i in range(26):
                if self.dfs(cur.children[i], word[1:]):
                    return True
        else:
            return self.dfs(cur.children[ord(word[0]) - ord('a')], word[1:])
        return False

# Your WordDictionary object will be instantiated and called as such:
# wordDictionary = WordDictionary()
# wordDictionary.addWord("word")
# wordDictionary.search("pattern")

###Java

class TrieNode {
    TrieNode[] children;
    boolean fill;
    public TrieNode() {
        fill = false;
        children = new TrieNode[26];
    }
}


public class WordDictionary {
    TrieNode root;
    
    public WordDictionary() {
        root = new TrieNode();
    }
    // Adds a word into the data structure.
    public void addWord(String word) {
        TrieNode node = root;
        for (char c: word.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
        }
        node.fill = true;
    }

    // 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) {
        TrieNode node = root;
        return dfs(root, word, 0);
    }
    
    public boolean dfs(TrieNode root, String word, int level) {
        if (root == null || (word.length() == level && !root.fill)) {
            return false;
        }
        if (word.length() == level && root.fill) {
            return true;
        }
        char cur = word.charAt(level);
        if (cur == '.') {
            for (int i = 0; i < 26; i++) {
                if (dfs(root.children[i], word, level + 1)) {
                    return true;
                }
            }
        } else {
            return dfs(root.children[cur - 'a'], word, level + 1);
        }
        
        return false;
    }
}

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

###Points

Related Posts