745. Prefix and Suffix Search

###Question Given many words, words[i] has weight i.

Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix). It will return the word with given prefix and suffix with maximum weight. If no word exists, return -1.

Examples:

Input: WordFilter([“apple”]) WordFilter.f(“a”, “e”) // returns 0 WordFilter.f(“b”, “”) // returns -1

Note:

1. words has length in range [1, 15000].
2. For each test case, up to words.length queries WordFilter.f may be made.
3. words[i] has length in range [1, 10].
4. prefix, suffix have lengths in range [0, 10].
5. words[i] and prefix, suffix queries consist of lowercase letters only.

Solution

• Method 1: String apis, startsWith, endsWith 3816 ms ```Java class WordFilter { private String[] words; public WordFilter(String[] words) { this.words = words; } public int f(String prefix, String suffix) { int res = -1; for(int i = 0; i < this.words.length; i++){ if(words[i].startsWith(prefix) && words[i].endsWith(suffix)){ res = Math.max(res, i); } } return res; } } /**
  • Your WordFilter object will be instantiated and called as such:
  • WordFilter obj = new WordFilter(words);
  • int param_1 = obj.f(prefix,suffix); */ ```
• Method 2: Use 2 trie tree to save the prefix and suffix. 570 ms
  1. When we are adding a word, we need to add it to both suffix tree and prefix tree.
  2. When we call the function f, we add all possible index of given prefix into a set.
  3. Then we check all possible words with given suffix, if set contains that value, this word has a chance to update the result.

       class WordFilter {
      private static class Node{
          boolean isLeaf;
          int index;
          Node[] childs;
          public Node(){
              this.childs = new Node[26];
              this.index = -1;
          }
      }
      private Node prefixRoot;
      private Node suffixRoot;
      private void insertPrefix(String word, int index){
          char[] arr = word.toCharArray();
          Node node = prefixRoot;
          for(int i = 0; i < arr.length; i++){
              int c = arr[i] - 'a';
              if(node.childs[c] == null){
                  node.childs[c] = new Node();
              }
              node = node.childs[c];
          }
          node.isLeaf = true;
          node.index = index;
      }
      private void insertSuffix(String word, int index){
          char[] arr = word.toCharArray();
          Node node = suffixRoot;
          for(int i = arr.length - 1; i >= 0; i--){
              int c = arr[i] - 'a';
              if(node.childs[c] == null){
                  node.childs[c] = new Node();
              }
              node = node.childs[c];
          }
          node.isLeaf = true;
          node.index = index;
      }
      public WordFilter(String[] words) {
          prefixRoot = new Node();
          suffixRoot = new Node();
          for(int i = 0; i < words.length; i++){
              insertPrefix(words[i], i);
              insertSuffix(words[i], i);
          }
      }
      public int f(String prefix, String suffix) {
          int res = -1;
          Set<Integer> set = new HashSet<>();
          findPrefix(prefix, set);
          return findSuffix(suffix, set);
      }
      private void findPrefix(String prefix, Set<Integer> set){
          char[] arr = prefix.toCharArray();
          Node node = this.prefixRoot;
          for(int i = 0; i < arr.length; i++){
              int c = arr[i] - 'a';
              if(node.childs[c] == null) return;
              else{
                  node = node.childs[c];
              }
          }
          addChilds(node, set);
      }
      public void addChilds(Node node, Set<Integer> set){
          if(node.isLeaf) set.add(node.index);
          for(int i = 0; i < 26; i++){
              if(node.childs[i] != null){
                  addChilds(node.childs[i], set);
              }
          }
      }
      private int findSuffix(String suffix, Set<Integer> set){
          char[] arr = suffix.toCharArray();
          Node node = this.suffixRoot;
          for(int i = arr.length - 1; i >= 0; i--){
              int c = arr[i] - 'a';
              if(node.childs[c] == null) return -1;
              else{
                  node = node.childs[c];
              }
          }
          return checkChilds(node, set);
      }
      public int checkChilds(Node node, Set<Integer> set){
          int res = -1;
          if(node.isLeaf && set.contains(node.index)){
              res = node.index;
          }
          for(int i = 0; i < 26; i++){
              if(node.childs[i] != null){
                  res = Math.max(res, checkChilds(node.childs[i], set));
              }
          }
          return res;
      }
       }
       /**
        * Your WordFilter object will be instantiated and called as such:
        * WordFilter obj = new WordFilter(words);
        * int param_1 = obj.f(prefix,suffix);
        */
     

• Method 3: Trie Tree
  • we construct a new word before inserting to tire tree.
  • Example: app, we save -app, p-app, pp-app, app-app, which contains all possible suffix conditions, since the question memtioned that word range is from 0 to 10.
• Method 4: Hashmap
  • we create two hashmaps(key is String of prefix or suffix, value is a list to save the word) to save all possible prefix and suffix.
  • Example: app
    • prefix map : a, ap, app
    • suffix map: p, pp, app