Using Trie - Algorithm

When to use trie
- prefix: findByPrefix

- Word search
X. Trie + DFS
LeetCode 212 - Word Search II
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 horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
https://discuss.leetcode.com/topic/33246/java-15ms-easiest-solution-100-00
public List findWords(char[][] board, String[] words) {
    List res = new ArrayList<>();
    TrieNode root = buildTrie(words);
    for(int i = 0; i < board.length; i++) {
        for(int j = 0; j < board[0].length; j++) {
            dfs(board, i, j, root, res);
        }
    }
    return res;
}

public void dfs(char[][] board, int i, int j, TrieNode p, List res) {
    char c = board[i][j];
    if(c == '#' || p.next[c - 'a'] == null) return;
    p = p.next[c - 'a'];
    if(p.word != null) {   // found one
        res.add(p.word);
        p.word = null;     // de-duplicate
    }

    board[i][j] = '#';
    if(i > 0) dfs(board, i - 1, j ,p, res); 
    if(j > 0) dfs(board, i, j - 1, p, res);
    if(i < board.length - 1) dfs(board, i + 1, j, p, res); 
    if(j < board[0].length - 1) dfs(board, i, j + 1, p, res); 
    board[i][j] = c;
}

public TrieNode buildTrie(String[] words) {
    TrieNode root = new TrieNode();
    for(String w : words) {
        TrieNode p = root;
        for(char c : w.toCharArray()) {
            int i = c - 'a';
            if(p.next[i] == null) p.next[i] = new TrieNode();
            p = p.next[i];
       }
       p.word = w;
    }
    return root;
}

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    String word;
}
https://codesolutiony.wordpress.com/2015/05/20/leetcode-word-search-ii/

LeetCode 425 - Word Squares
Given a set of words (without duplicates), find all word squares you can build from them.

LeetCode 472 - Concatenated Words
Given a list of words, please write a program that returns all concatenated words in the given list of words.

LeetCode 30 - Substring with Concatenation of All Words
You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

X. - Sliding window
https://discuss.leetcode.com/topic/6617/an-o-n-solution-with-detailed-explanation/10

LeetCode 30 - Substring with Concatenation of All Words

TODO
LeetCode 336 - Palindrome Pairs
Given a list of unique words. Find all pairs of indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

LeetCode 421 - Maximum XOR of Two Numbers in an Array
Trie[] children = new Trie[2];
X. https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap
O(32n) -> bit by bit

Uber Prepare: Web Address

LeetCode 527 - Word Abbreviation
Given an array of n distinct non-empty strings, you need to generate minimal possible abbreviations for every word following rules.

Airbnb: K Edit Distance
Given a list of word and a target word, output all the words for each the edit distance with the target no greater than k.

Leetcode 211 - Add and Search Word
LeetCode 212 - Word Search II
Given a 2D board and a list of words from the dictionary, find all words in the board.

Leetcode 211 - Add and Search Word
Trie: https://discuss.leetcode.com/topic/14030/my-simple-and-clean-java-code

LeetCode 30 - Substring with Concatenation of All Words
You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
https://discuss.leetcode.com/topic/6593/accepted-recursive-solution-using-trie-tree
      static class TrieNode {
           int value = 0;
           Map children = new HashMap();
       }

       TrieNode trie;

    // build a trie tree
    public List findSubstring(String S, String[] L) {
        trie = buildTrie(L);
        int length = getTotalLength(L);
        List result = new LinkedList();
        for (int i = 0; i < S.length() - length + 1; i++) {
            if (isSubString(S, i, i + length))
                result.add(i);
        }
        return result;
    }
    
    private int getTotalLength(String[] L) {
        int sum = 0;
        for (String l : L)
            sum += l.length();
        return sum;
    }
    
    private TrieNode buildTrie(String[] L) {
        TrieNode root = new TrieNode();
        for (String l : L)
            addWord(root, l);
        return root;
    }
    
    private void addWord(TrieNode root, String s) {
        TrieNode node = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            TrieNode next = node.children.get(c);
            if (next == null) {
                next = new TrieNode();
                node.children.put(c, next);
            }
            node = next;
        }
        node.value++;
    }
    
    private boolean isSubString(String S, int start, int end) {
     if (start == end)
      return true;
        // search in the trie tree
        TrieNode node = trie;
        for (int i = start; i < end; i++) {
            char c = S.charAt(i);
            if (node.children.get(c) == null)
                return false;
            node = node.children.get(c);
            if (node.value > 0) {  // leaf & can be used
                node.value--; // mark as used
                if (isSubString(S, i + 1, end)) {
                    node.value++; // mark as unused
                    return true;
                }
                node.value++; // mark as unused
            }
        }
        return false;
    }
X. Using Suffix Trie
Given a string band an array of smaller strings T, design a method to search b for each small string in T.
https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2017.%20Hard/Q17_17_Multi_Search/TrieNode.java
https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2017.%20Hard/Q17_17_Multi_Search/QuestionB.java
X. https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2017.%20Hard/Q17_17_Multi_Search/QuestionC.java

Trie implementation
http://blog.csdn.net/ljiabin/article/details/45846527
  1. class TrieNode {  
  2.     public TrieNode[] children = new TrieNode[26];  
  3.     public String item = "";        
  4.     public TrieNode() {  
  5.     }  
  6. }  
  7.   
  8. class Trie {  
  9.     private TrieNode root;  
  10.   
  11.     public Trie() {  
  12.         root = new TrieNode();  
  13.     }  
  14.   
  15.     // Inserts a word into the trie.  
  16.     public void insert(String word) {  
  17.         TrieNode node = root;  
  18.         for (char c : word.toCharArray()) {  
  19.             if (node.children[c - 'a'] == null) {  
  20.                 node.children[c - 'a'] = new TrieNode();  
  21.             }  
  22.             node = node.children[c - 'a'];  
  23.         }  
  24.         node.item = word;  
  25.     }  
  26.   
  27.     // Returns if the word is in the trie.  
  28.     public boolean search(String word) {  
  29.         TrieNode node = root;  
  30.         for (char c : word.toCharArray()) {  
  31.             if (node.children[c - 'a'] == nullreturn false;  
  32.             node = node.children[c - 'a'];  
  33.         }  
  34.         return node.item.equals(word);  
  35.     }  
  36.   
  37.     // Returns if there is any word in the trie  
  38.     // that starts with the given prefix.  
  39.     public boolean startsWith(String prefix) {  
  40.         TrieNode node = root;  
  41.         for (char c : prefix.toCharArray()) {  
  42.             if (node.children[c - 'a'] == nullreturn false;  
  43.             node = node.children[c - 'a'];  
  44.         }  
  45.         return true;  
  46.     }  
  47. }  

Post a Comment

Labels

Java (159) Lucene-Solr (111) Interview (61) All (58) J2SE (53) Algorithm (45) Soft Skills (37) Eclipse (33) Code Example (31) Linux (24) JavaScript (23) Spring (22) Windows (22) Web Development (20) Nutch2 (18) Tools (18) Bugs (17) Debug (16) Defects (14) Text Mining (14) J2EE (13) Network (13) Troubleshooting (13) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) Problem Solving (9) UIMA (9) html (9) Http Client (8) Maven (8) Security (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) ANT (6) Coding Skills (6) Database (6) Scala (6) Shell (6) css (6) Algorithm Series (5) Cache (5) Dynamic Languages (5) IDE (5) Lesson Learned (5) Programmer Skills (5) System Design (5) Tips (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Spark (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) How to Interview (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Python (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts