[LC] 792. Number of Matching Subsequences

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:

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

Solution 1: TLE

class Solution {
    public int numMatchingSubseq(String S, String[] words) {
        int res = 0;
        for (String word: words) {
            int wordIndex = 0;
            for (int i = 0; i < S.length(); i++) {
                if (S.charAt(i) == word.charAt(wordIndex)) {
                    wordIndex += 1;
                }
                if (wordIndex == word.length()) {
                    res += 1;
                    break;
                }
            }
        }
        return res;
    }
}

Solution 2:

class Solution {
    public int numMatchingSubseq(String S, String[] words) {
        int res = 0;
        List<Integer>[] indexArr = getIndex(S);
        for (String word: words) {
            int curIndex = 0;
            for (int i = 0; i < word.length(); i++) {
                curIndex = getPos(indexArr[word.charAt(i) - 'a'], curIndex);
                if (curIndex == -1) {
                    break;
                }
                curIndex += 1;
            }
            if (curIndex != -1) {
                res += 1;
            }
        }
        return res;
    }
    
    private List<Integer>[] getIndex(String str) {
        List<Integer>[] indexArr = new List[26];
        for (int i = 0; i < str.length(); i++) {
            if (indexArr[str.charAt(i) - 'a'] == null) {
                indexArr[str.charAt(i) - 'a'] = new ArrayList<>();
            }
            indexArr[str.charAt(i) - 'a'].add(i);
        }
        return indexArr;
    }
    
    private int getPos(List<Integer> list, int cur) {
        if (list == null) {
            return -1;
        }
        int left = 0;
        int right = list.size() - 1;
        if (list.get(left) >= cur) {
            return list.get(left);
        }
        if (list.get(right) < cur) {
            return -1;
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) == cur) {
                return list.get(mid);
            } else if (list.get(mid) < cur) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return list.get(left);
    }
}