Array-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].
============================================
class Solution {

	public int numMatchingSubseq(String S, String[] words) {
		TreeSet<Integer>[] poss = new TreeSet[26];
		for (int i = 0; i < 26; i++) {
			poss[i] = new TreeSet();
		}

		for (int i = 0; i < S.length(); i++) {
			poss[S.charAt(i) - 'a'].add(i); //使用TreeSet来寻找大于等于某个数的最小数
		}

		Map<String, Boolean> results = new HashMap<>();
		int count = 0;
		for (String str : words) {
			if (exists(results, str, poss))
				count++;
		}
		return count;
	}

	public boolean exists(Map<String, Boolean> results, String str, TreeSet<Integer>[] poss) {
		Boolean b = results.get(str); //在HashMap中比较字符串
		if (b != null)
			return b;

		Integer nextPos = 0;
		int i = 0;
		for (; i < str.length(); i++) {
			nextPos = poss[str.charAt(i) - 'a'].ceiling(nextPos);
			if (nextPos == null) {
				results.put(str, false);
				return false;
			}
			nextPos++;
		}
		results.put(str, true);
		return true;
	}
}
//32%, 使用TreeSet来加速查询和使用HashMap来存储结果, 效率反而没有单独使用HashMap高
//一个方面是使用了额外的空间和额外的操作
//另一个方面可能是word比较短, 而且有很多重复