给定字符串S和一个字符串数组，求数组中有多少个字符串是S的子字符串，子字符串的定义是可以母串可以通过删减元素成为子串。

方法一：

首先想到的就是双指针法，对字符串中的每个元素进行匹配操作，来判断是否为字字符串，想想都知道会超时的。

class Solution:
    def numMatchingSubseq(self, S, words):
        """
        :type S: str
        :type words: List[str]
        :rtype: int
        """
        cont = 0
        for word in words:
            if self.isSubseq(S, word):
                cont += 1
        return cont

    def isSubseq(self, s, word):
        index = 0
        for i in s:
            if i == word[index]:
                index += 1
            if index == len(word):
                break
        return index == len(word)

方法二：

首先分析下上述方法超时的原因，因为对于每一个字符串，母串都要从头开始遍历一次，这时候是母串跟着子串走。我们可以倒过来，让子串跟着母串走，遍历母串，能匹配到子串的首字符就将子串进行砍头操作后保存，然后再匹配母串后面的字符，砍成空串说明能匹配的上。用字典存储，以空间换时间。
举个例子：
S= abcde
words = ["a","ac"]
从左到右遍历S，对于首字母a,
words更新为["","c"],
b不在words中，
对于c,words更新为["',""],
都为空，匹配结束

class Solution:
    def numMatchingSubseq(self, S, words):
        import  collections
        dictionary = collections.defaultdict(list)
        res = 0
        for word in words:
            dictionary[word[0]].append(word[1:])
        for s in S:
            length = len(dictionary[s])
            for i in range(length):
                if len(dictionary[s][i])==0:
                    res +=1
                else:
                    dictionary[dictionary[s][i][0]].append(dictionary[s][i][1:])
            dictionary[s] = dictionary[s][length:]
        return res

这里要注意字典的时候要删除原有的元素，所以先要把key对应的数组长度记录下来后才能进行append操作，操作完根据记录的长度进行删除操作。这不免有些麻烦，可以使用python的迭代器和生成器来完成这一功能。
优化过的代码如下

class Solution:
    def numMatchingSubseq(self, S, words):
        import collections
        dictionary = collections.defaultdict(list)
        for word in words:
            dictionary[word[0]].append(iter(word[1:]))
        for s in S:
            for it in dictionary.pop(s, ()):
                dictionary[next(it,None)].append(it)
        return len(dictionary[None])