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)