Design Add and Search Words Data Structure

 Problem

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.

Solution

The fastest word insert and retrieving datastructure we know so far is R-way trie. So lets do it.

import java.util.*;

class Solution {

  public static void main(String...args) {

    WordDictionary wordDictionary = new WordDictionary();

    wordDictionary.addWord("bad");

    wordDictionary.addWord("dad");

    wordDictionary.addWord("mad");

    System.out.println(wordDictionary.search("pad")); // return False

    System.out.println(wordDictionary.search("bad")); // return True

    System.out.println(wordDictionary.search(".ad")); // return True

    System.out.println(wordDictionary.search("b..")); // return True

    System.out.println(wordDictionary.search("c..")); // return False

  }

}

class WordDictionary {

    private static class Node {

      Node[] next = new Node[26];

      boolean isEnd;

    }

  

    Node root;

    /** Initialize your data structure here. */

    public WordDictionary() {

        root = new Node();

    }

    

    /** Adds a word into the data structure. */

    public void addWord(String word) {

        addNode(root, word, 0);

    }

  

    private void addNode(Node node, String word, int n) {

      if(n == word.length()) 

        return;

      int pos = word.charAt(n) - 'a';

      Node next = node.next[pos];

      if(next == null) {

        next = new Node();

        node.next[pos] = next;

      }

      if(n == word.length() - 1) {

        next.isEnd = true;

      }

      addNode(next, word, n+1);

    }

    

    /** 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(root, word, 0);

    }

   

    private boolean search(Node node, String word, int n) {

      if(n == word.length())

        return true;

      char c = word.charAt(n);

      if(c == '.') {

        if(n == word.length() - 1) {

          for(Node cur : node.next) {

            if(cur != null && cur.isEnd) {

              return true;

            }

          }

          return false;

        }

        for(Node cur : node.next) {

          if(cur != null && search(cur, word.substring(n+1), 0)) {

            return true;

          }

        }

        return false;

      } else {

        int pos = c - 'a';

        Node next = node.next[pos];

        if(next == null) {

          return false;

        } else {

          if(n == word.length() - 1) {

            return next.isEnd;

          }

          return search(next, word, n+1);

        }

      }

        

    }

}

The time complexity for insert is O(w), where w is the word length. The space complexity for insert is O(w) we need to create w new node.

The time complexity for search hit a normal word is O(w), because we processed each character. The search miss for normal word is O(1) on average. The space complexity for search a normal word is O(w), which proportional to caller stack depth. 

The time complexity for searching a . word is O(wN) where N is the number of keys in the dictionary. In the worst case an all .... search will exam all the possible pass in the dictionary. The space complexity is O(w) which is proportional to caller stack depth.

Implement Trie (Prefix Tree)

 Problem

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");

trie.search("apple");   // returns true

trie.search("app");     // returns false

trie.startsWith("app"); // returns true

trie.insert("app");   

trie.search("app");     // returns true

Note:

You may assume that all inputs are consist of lowercase letters a-z.

All inputs are guaranteed to be non-empty strings.

Solution

Trie data structure is a multi-node tree. While tree Node as 2 child node, trie node has 26 child node stored in an array. It has an additional boolean field marking the end of a word.

import java.util.*;

class Solution {

  public static void main(String...args) {

    Trie trie = new Trie();

    trie.insert("apple");

    System.out.println(trie.search("apple"));   // returns true

    System.out.println(trie.search("app"));     // returns false

    System.out.println(trie.startsWith("app")); // returns true

    trie.insert("app");   

    System.out.println(trie.search("app"));     // returns true

  }

}

class Trie {

    TrieNode root;

    private static class TrieNode {

      TrieNode[] next = new TrieNode[26];

      boolean isEnd = false;

    }

    /** Initialize your data structure here. */

    public Trie() {

      root = new TrieNode();

    }

    

    /** Inserts a word into the trie. */

    public void insert(String word) {  //apple

      insert(root, word, 0);

    }

  

    private void insert(TrieNode node, String word, int n) {  //1

      if(n == word.length()) {

        return;

      }

      int p = word.charAt(n) - 'a';

      TrieNode next = node.next[p];

      if(next == null) {

        next = new TrieNode();

        node.next[p] = next;

      }

      if(n == word.length() - 1) {

        next.isEnd = true;

      }

      insert(next, word, n+1);

    }

    

    /** Returns if the word is in the trie. */

    public boolean search(String word) {

      return search(root, word, 0);

    }

  

    private boolean search(TrieNode node, String word, int n) {

      int p = word.charAt(n) - 'a';

      TrieNode next = node.next[p];

      if(next == null) {

        return false;

      } else {

        if(n == word.length() - 1) {

          return next.isEnd;

        }

        return search(next, word, n+1);

      }

    }

  

    /** Returns if there is any word in the trie that starts with the given prefix. */

    public boolean startsWith(String prefix) {

      return startsWith(root, prefix, 0);

    }

  

    private boolean startsWith(TrieNode node, String word, int n) {

      int p = word.charAt(n) - 'a';

      TrieNode next = node.next[p];

      if(next == null) {

        return false;

      } else {

        if(n == word.length() - 1) {

          return true;

        }

        return startsWith(next, word, n+1);

      }

    }

}

The time complexity is O(w) for all 3 operations, where w is the length of word. We need to process each character in the word of length w.

The space complexity is O(w) for all 3 operations. 

• For insert, we create w TrieNode, TrieNode has a size 26 array and a boolean field, we assume its size is constant. 
• For search and startsWith, the recursive call stack is w layer deep, so the space also proportional to O(w).

Replace Words

Problem

In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Solution

We can break the sentence into words, then look up the dictionary. The performance is depends on how to implement dictionary look up. Brutal force is for each word, we can loop through the dictionary words to find a match. The time cost will be N*M*word-length*root-length. HashMap or Trie allow fast string lookup. If we use HashSet, we need to check all the substrings word.substring(0, i) to make sure one of those substrings match a dictionary word. The time cost will be O(Sum-of-N(word-length^2)), the space will be the O(N*word-length + M*root-length) for storing the N words in the sentence the M roots in the dictionary. With Trie, we can find shortest prefix in time proportional to the total number of characters in the N words. The space is the storage for the words and the dictionary. 

class RootReplace {
  private static Trie trie = new Trie();
  public static String replace(String[] dict, String sentence) {
    String[] words = sentence.split(" ");
    StringBuilder sb = new StringBuilder();
    int N = words.length;
    for(int i = 0; i < N; i++) {
      String word = words[i];
      String pre = trie.shortestPrefix(word);
      sb.append(pre == null ? word : pre).append(" ");
    }
    return sb.toString();
  }
  public static void main(String...args) {
    String sentence = "the cattle was rattled by the battery";
    String[] dict = new String[]{"cat", "bat", "rat"};
    for(String pre : dict) {
      trie.put(pre, pre);
    }
    System.out.println(replace(dict, sentence));
  }

  private static class Trie {
    private static int R = 26;
    private Node root;
    private static class Node {
      Node[] next = new Node[R];
      String val;
    }
    public void put(String key, String val) {
      root = put(root, key, val, 0);
    }
    private Node put(Node root, String key, String val, int d) {
      Node x = root;
      if(x == null)
        x = new Node();
      if(key.length() == d) {
        x.val = val;
        return x;
      }
      char c = key.charAt(d);
      x.next[c - 'a'] = put(x.next[c - 'a'], key, val, d+1);
      return x;
    }
    public String shortestPrefix(String key) {
      return shortestPrefix(root, key, 0);
    }
    private String shortestPrefix(Node root, String key, int d) {
      if(root == null) return null;
      if(root.val != null) return root.val;
      if(key.length() == d) return null;
      char c = key.charAt(d);
      return shortestPrefix(root.next[c - 'a'], key, d+1);
    }
  }
}

Time cost O(N*word-length). Space cost O(N*word-length + (8R + 56)M*root-length)