792. Number of Matching Subsequences

Question

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

Example :
Input: 
S = "abcde"
words = ["a", "bb", "acd", "ace"]
Output: 3
Explanation: There are three words in words that are a subsequence of S: "a", "acd", "ace".

Note:

  1. All words in words and S will only consists of lowercase letters.
  2. The length of S will be in the range of [1, 50000].
  3. The length of words will be in the range of [1, 5000].
  4. The length of words[i] will be in the range of [1, 50].

Solutions:

  • Method 1: 
      class Solution {
      private int sLen;
      private String s;
      public int numMatchingSubseq(String S, String[] words) {
          sLen = S.length();
          s = S;
          int res = 0;
          for(String t : words){
              if(isSub(t)) res++;
          }
          return res;
      }
      private boolean isSub(String t){
          int tLen = t.length();
          int index1 = 0, index2 = 0;
          while(index1 < tLen && index2 < sLen){
              if(s.charAt(index2) == t.charAt(index1)){
                  index1++;
              }
              index2++;
          }
          return index1 == tLen;
      }
  }
  • Method 2: HashMap + Binary search 
      class Solution {
      private Map<Character, List<Integer>> map;
      public int numMatchingSubseq(String S, String[] words) {
          this.map = new HashMap<>();
          for(int i = 0; i < S.length(); i++){
              char c = S.charAt(i);
              List<Integer> list = map.containsKey(c) ? map.get(c): new ArrayList<>();
              list.add(i);
              map.put(c, list);
          }
          int res = 0;
          for(String word : words){
              if(match(word)) res++;
          }
          return res;
      }
      private boolean match(String s){
          char[] arr = s.toCharArray();
          int pre = -1;
          for(char c : arr){
              if(!map.containsKey(c)) return false;
              List<Integer> list = map.get(c);
              int index = Collections.binarySearch(list, pre + 1);
              if(index < 0) index = -index - 1;
              if(index >= list.size()) return false;
              pre = list.get(index);
          }
          return true;
      }
  }