745. Prefix and Suffix Search.md

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

   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.

  class Trie{
  private:
  	struct Node{
  		vector<Node*> childs;
  		int index;
  		Node(): index(-1), childs(27, nullptr){};
  		~Node(){
  			for(auto node: childs){
  				delete node;
  			}
  		}
  	};
  	Node* find(const string & s){
  		Node* temp = root_.get();
  		for(const char & c: s){
  			if(!temp->childs[c - 'a']) return nullptr;
  			temp = temp->childs[c - 'a'];
  		}
  		return temp;
  	}
  	unique_ptr<Node> root_;
  public:
  	Trie(): root_(new Node()){};
  	void insert(const string & word, int index){
  		Node* temp = root_.get();
  		for(const char & c: word){
  			if(!temp->childs[c - 'a']){
  				temp->childs[c -'a'] = new Node();
  			}
  			temp = temp->childs[c - 'a'];
  			temp->index = index;
  		}
  	}
  	
  	int startWith(const string & s){
  		auto node = find(s);
  		if(!node) return -1;
  		return node->index;
  	}
  };
  class WordFilter {
  private:
  	Trie trie_;
  public:
  	WordFilter(vector<string>& words) {
  		int size = words.size();
  		for(int i = 0; i < size; ++i){
  			const string word = words[i];
  			int len = word.length();
  			for(int j = len; j >= 0; j--)
  				trie_.insert(word.substr(j, len) + "{" + word, i);
  		}
  	}
  	
  	int f(string prefix, string suffix) {
  		return trie_.startWith(suffix + "{" + prefix);
  	}
  };
  /**
   * Your WordFilter object will be instantiated and called as such:
   * WordFilter* obj = new WordFilter(words);
   * int param_1 = obj->f(prefix,suffix);
   */

• 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

   class WordFilter {
   public:
   	WordFilter(vector<string>& words) {
   		int size = words.size();
   		for(int k = 0; k < size; ++k){
   			string word = words[k];
   			int len = word.length();
   			for(int i = 0; i <= len; ++i){
   				string prefix = word.substr(0, i);
   				for(int j = len; j >= 0; --j){
   					string key = prefix + "_" + word.substr(j, len);
   					map_[key] = k;
   				}
   			}
   		}
   	}
   	int f(string prefix, string suffix) {
   		auto ptr = map_.find(prefix + "_" + suffix);
   		if(ptr == map_.end()) return -1;
   		return ptr->second;
   	}
   private:
   	unordered_map<string, int> map_;
   };
   /**
    * Your WordFilter object will be instantiated and called as such:
    * WordFilter* obj = new WordFilter(words);
    * int param_1 = obj->f(prefix,suffix);
    */