Python程式：查詢單詞列表中存在的子序列個數

Python 伺服器端程式設計程式設計

假設我們有一個單詞列表和一個字串s，我們需要找到單詞列表中作為s的子序列的字串的個數。

因此，如果輸入類似於 words = ["xz", "xw", "y"] s = "xyz"，則輸出將為 2，因為 "xz" 和 "y" 是 "xyz" 的子序列。

為了解決這個問題，我們將遵循以下步驟：

ans := 0
d := 一個空字典
對於words中的每個單詞，執行：
- 將單詞插入到d[word[0]]的末尾
對於s中的每個字元c，執行：
- l := d[c]
- d[c] := 一個新的列表
- 對於l中的每個單詞，執行：
  - 如果單詞的長度為1，則
    - ans := ans + 1
  - 否則，
    - 將單詞的子字串（從索引1到結尾）插入到d[word[1]]的末尾
返回ans

讓我們看看下面的實現來更好地理解：

示例

線上演示

from collections import defaultdict
class Solution:
   def solve(self, words, s):
      ans = 0

      d = defaultdict(list)
      for word in words:
         d[word[0]].append(word)

      for c in s:
         l = d[c]
         d[c] = []

         for word in l:
            if len(word) == 1:
               ans += 1
            else:
               d[word[1]].append(word[1:])
      return ans
ob = Solution()
words = ["xz", "xw", "y"]
s = "xyz"
print(ob.solve(words, s))

輸入

["xz", "xw", "y"], "xyz"

輸出

Arnab Chakraborty

更新於：2020-12-02

345 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習