LeetCodeブラシノート792:マッチングサブシーケンスの単語数(Python実装)

タイトルの説明:
与えられた文字列Sと単語辞書wordsは、words[i]のうちSのサブシーケンスである単語の個数を求める.

  :
  : 
S = "abcde"
words = ["a", "bb", "acd", "ace"]
  : 3
  :      S        : "a", "acd", "ace"。

注意:

wordsとSの単語はすべて小文字で構成されています.

Sの長さは[1, 50000]である.

wordsの長さは[1, 5000]である.

words[i]の長さは[1, 50]である.

考え方:1
暴力解読:
メインループはwords、サブループはSで、Sの各アルファベットとwordsの各wordのアルファベットでマッチングし、あるビット値が等しい場合は、それぞれ1つの位置にジャンプします.等しくない場合、Sのアルファベットだけが次の位置にジャンプして一致し続けます.words内の単一wordを遍歴するまでカウンタ+1

class Solution:
    def numMatchingSubseq(self,words,S):
        i,j = 0,0
        count = 0
        for w in words:
            while(i < len(w) and j < len (S)):
                if S[j] == w[i]:
                    i+=1
                    j+=1
                else:
                    j+=1
            if i == len(w):
                count+=1
        return count

考え方:2
wordsを観察するときに、待機リストを定義することができます.例えば、wordsでは「a」、「acd」、「ace」はaで始まり、「bb」はbで始まります.Sを巡回すると、aで始まるwordがSのアルファベットaに一致し、Sが後ろに移動し、2番目のアルファベットbの場合、bで始まる「bb」がそのアルファベットbに一致する.その後、wordごとに一致するアルファベットを削除し、保存します.wordが完全に削除された場合(例えば「a」が最初に一致したときに完全に一致する)、各wordを1つのlistに格納し、最後にこのlistの長さを計算すればよい.
詳細手順:
初期時:

S = "abcde" 
words = ["a", "bb", "acd", "ace"]

wordsの各wordの最初のアルファベット:“a”、“acd”、“ace”はすべてaで、“bb”はbで、Sの中でaとbがマッチングする必要があります

'a':  ["(a)", "(a)cd", "(a)ce"]
'b':  ["(b)b"]

Sを巡回し続け、Sの頭文字はaであり、「a」、「acd」、「ace」の頭文字と一致し、aを保存して次の一致する文字を待つことができ、同じb

'b':  ["(b)b"]
'c':  ["a(c)d", "a(c)e"]
None: ["a"]

「a」はマッチングが完了したため、「acd」と「ace」はcが必要であり、「bb」はbが必要である

'b':  ["b(b)"]
'c':  ["a(c)d", "a(c)e"]
None: ["a"]

そしてSでもc文字に一致します

'b':  ["b(b)"]
'd':  ["ac(d)"]
'e':  ["ac(e)"]
None: ["a"]

同じ理屈、d文字:

'b':  ["b(b)"]
'e':  ["ac(e)"]
None: ["a", "acd"]

同じ理屈、e文字:

'b':  ["b(b)"]
None: ["a", "acd", "ace"]

最後にNoneというリストの長さを返すだけでいいです
コード:

class Solution:
    def numMatchingSubseq(self, S, words):
        """
        :type S: str
        :type words: List[str]
        :rtype: int
          ：
        S = "abcde"
        words = ["a", "bb", "acd", "ace"]
        """
        waiting = collections.defaultdict(list)
        for w in words:
            waiting[w[0]].append(iter(w[1:]))
        for c in S:
            for it in waiting.pop(c, ()):
                waiting[next(it, None)].append(it)
        return len(waiting[None])