LIKE CODING: Trie

Showing posts with label Trie. Show all posts

Saturday, March 12, 2016

LeetCode [336] Palindrome Pairs

Wednesday, October 21, 2015

MJ [44] Find the Longest Substring

Question:
Give a dictionary "dict" and a string "S", find the longest valid word in dict which is a substring of "S".
Eg. dict = {"abc", "defgh", "ef"}
S = "adbecfgh".
It should return "defgh".

Ref
[1] http://www.mitbbs.com/article_t/JobHunting/32960525.html

Monday, October 19, 2015

MJ [42] Find area code

Question:
+1 North America
...
+1950 Northern Cal
…
+44 UK
+4420 London
+447 UK Mobile
+44750 Vodafoned
…

and we have a phone number, for instance
+447507439854795
+44989045454

return where the number is from

Ref
[1] http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=101580&ctid=92

Saturday, August 29, 2015

MJ [30] Longest Words in a Dictionary

Question:
Find the longest words in a dictionary of legal words that can be constructed from a given list of letters. The dictionary is give by ospd.txt.
$ ./test ospd.txt i g h l p r a
ret :argil glair grail graph hilar laigh phial pilar ralph
ret_trie:argil glair grail graph hilar laigh phial pilar ralph

Ref

[1] https://www.reddit.com/r/Python/comments/n3arf/python_quiz_of_the_week_1/
[2] http://codereview.stackexchange.com/questions/6634/longest-words-in-dictionary-that-can-be-constructed-from-a-list-of-letters

Tuesday, May 26, 2015

LeetCode [212] Word Search II

212. Word Search II

Hard

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Constraints:

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] is a lowercase English letter.
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
All the strings of words are unique.

class TrieNode{
public:
    char key;
    bool isTail = false;
    TrieNode* children[26] = {NULL};
    TrieNode(){}
    TrieNode(char k):key(k){}
};

class Trie{
public:
    TrieNode * root = new TrieNode();
    Trie(){}
    void insert(string word){
        TrieNode *p = root;
        for(char c:word){
            if(p->children[c-'a']==NULL){
                p->children[c-'a'] = new TrieNode(c);
            }
            p = p->children[c-'a'];
        }
        p->isTail = true;
    }
};

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        Trie trie;
        for(string w:words) trie.insert(w);
        vector<string> ret;
        int m = board.size(), n = board[0].size();
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                dfs(i, j, m, n, board, trie.root, ret, "");
            }
        }
        return ret;
    }
   void dfs(int i, int j, int m, int n, vector<vector<char>>& board, TrieNode *t, vector<string> &ret, string cur){
            char c = board[i][j];
            board[i][j] = '#';
            if(c!='#' && t->children[c-'a']!=NULL){
                cur += c;
                if(t->children[c-'a']->isTail){
                    ret.push_back(cur);
                    t->children[c-'a']->isTail = false;
                }
                if(i-1>=0) dfs(i-1, j, m, n, board, t->children[c-'a'], ret, cur);
                if(i+1<m)  dfs(i+1, j, m, n, board, t->children[c-'a'], ret, cur);
                if(j-1>=0) dfs(i, j-1, m, n, board, t->children[c-'a'], ret, cur);
                if(j+1<n)  dfs(i, j+1, m, n, board, t->children[c-'a'], ret, cur);

            }
            board[i][j] = c;
    }

};

class Solution {
    int[][] dirs = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    class Trie{
        boolean isEnd;
        Trie[] children = new Trie[26];
    }

    int m, n;
    Trie root;
    void insert(String w){
        Trie p = root;
        for(char c : w.toCharArray()){
            if(p.children[c-'a']==null){
                p.children[c-'a'] = new Trie();
            }
            p = p.children[c-'a'];
        }
        p.isEnd = true;
    }

    public List<String> findWords(char[][] board, String[] words) {
        m = board.length;
        n = board[0].length;
        root = new Trie();
        for(String w : words) insert(w);
        Set<String> set = new HashSet<>();
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                Trie p = root;
                char c = board[i][j];
                if(p.children[c-'a']!=null){
                    board[i][j] = '.';
                    String cur = ""+c;
                    search(i, j, board, set, p.children[c-'a'], cur);
                    board[i][j] = c;
                }
            }
        }

        List<String> list = new ArrayList<>(set);
        return list;
    }

    void search(int i, int j, char[][] board, Set<String> set, Trie p, String cur){
        if(p.isEnd) set.add(cur);
        for(int[] d : dirs){
            int ii = i+d[0], jj = j+d[1];
            if(ii>=0 && ii<m && jj>=0 && jj<n && board[ii][jj]!='.'){
                char c = board[ii][jj];
                if(p.children[c-'a']!=null){
                    board[ii][jj] = '.';
                    search(ii, jj, board, set, p.children[c-'a'], cur+c);
                    board[ii][jj] = c;
                }
            }
        }
    }
}

Friday, May 15, 2015

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

211. Design Add and Search Words Data Structure

Medium

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
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

Constraints:

1 <= word.length <= 500
word in addWord consists lower-case English letters.
word in search consist of '.' or lower-case English letters.
At most 50000 calls will be made to addWord and search.

//C++: 46ms
class TrieNode {
public:
    bool isTail;
    char key;
    unordered_map<char, TrieNode*> children;

    // Initialize your data structure here.
    TrieNode():isTail(false){}
    TrieNode(char k):isTail(false),key(k){}
    
    bool findChild(char ch){
        return children.find(ch)!=children.end();
    }
    TrieNode * insertChildrend(char ch){
        TrieNode *newNode = new TrieNode(ch);
        children.insert(pair<char, TrieNode*>(ch, newNode));
        return newNode;
    }
    TrieNode * getChild(char ch){
        return children[ch];
    }
};


class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    void insert(string s) {
        TrieNode *p = root;
        for(auto ch:s){
            if(!p->findChild(ch)){
                TrieNode *newNode = p->insertChildrend(ch);
                p = newNode;
            }else{
                p = p->getChild(ch);
            }
        }
        if(p!=NULL){
            p->isTail = true;
        }
    }

    // Returns if the word is in the trie.
    bool search(string key, TrieNode *p, int index) {
        if(index>key.size()) return false;
        if(index==key.size()){
            if(p!=NULL && p->isTail) return true;
            else return false;
        }
        char ch = key[index];
        if(ch!='.'){
            if(p==NULL || !p->findChild(ch)){
                return false;
            }
            TrieNode *q = p->getChild(ch);
            return search(key, q, index+1);
        }else{
            for(auto it=p->children.begin(); it!=p->children.end(); ++it){
                TrieNode *q = it->second;
                if(search(key, q, index+1)) return true;
            }
            return false;
        }
    }    

    TrieNode* root;
};


class WordDictionary {
    Trie trie;
public:
    WordDictionary(){
        Trie trie=Trie();
    }

    // Adds a word into the data structure.
    void addWord(string word) {
       trie.insert(word);
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        return  trie.search(word, trie.root, 0);
    }
};

class TrieNode{
public:
    char key;
    bool isLeaf = false;
    TrieNode* children[26] = {NULL};
    TrieNode(){}
    TrieNode(char k):key(k){}
};

class Trie{
public:
    TrieNode *root = new TrieNode();
    Trie(){}
    void insert(string s){
        TrieNode *p = root;
        for(int i=0; i<(int)s.size(); ++i){
            char c = s[i];
            if(p->children[c-'a']==NULL){
                p->children[c-'a'] = new TrieNode(c);
            }
            p = p->children[c-'a'];
        }
        p->isLeaf = true;
    }

    bool search(string s){
        return search(s, s.size(), 0, root);
    }
    bool search(string s, int n, int i, TrieNode* p){
        if(i==n){
            return p->isLeaf;
        }else{
            char c = s[i];
            if(c!='.'){
                return p->children[c-'a']&&search(s, n, i+1, p->children[c-'a']);
            }else{
                for(char cc='a'; cc<='z'; ++cc){
                    if(p->children[cc-'a']&&search(s, n, i+1, p->children[cc-'a'])) return true;
                }
            }
            return false;
        }
    }
};

class WordDictionary {
    Trie trie;
public:

    // Adds a word into the data structure.
    void addWord(string word) {
        trie.insert(word);
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        return trie.search(word);
    }
};

Wednesday, May 13, 2015

LeetCode [208] Implement Trie (Prefix Tree)

208. Implement Trie (Prefix Tree)

Medium

Trie (we pronounce "try") or prefix tree is a tree data structure used to retrieve a key in a strings dataset. There are various applications of this very efficient data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() initializes the trie object.
void insert(String word) inserts the string word to the trie.
boolean search(String word) returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Constraints:

1 <= word.length, prefix.length <= 2000
word and prefix consist of lowercase English letters.
At most 3 * 104 calls will be made to insert, search, and startsWith.

class Trie {
    class TrieNode{
        boolean isEnd;
        TrieNode[] children;
        TrieNode(){
            isEnd = false;
            children = new TrieNode[26];
        }
    }
    TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode p = root;
        for(char c : word.toCharArray()){
            if(p.children[c-'a']==null){
                p.children[c-'a'] = new TrieNode();
            }
            p = p.children[c-'a'] ;
        }
        p.isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode p = root;
        for(char c : word.toCharArray()){
            if(p.children[c-'a']==null){
                return false;
            }
            p = p.children[c-'a'] ;
        }
        return p.isEnd == true;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode p = root;
        for(char c : prefix.toCharArray()){
            if(p.children[c-'a']==null){
                return false;
            }
            p = p.children[c-'a'] ;
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */