Python程式：檢查字串能否被給定單詞列表分解

假設我們有一個單詞列表和另一個沒有空格的字串s。我們必須檢查該字串是否可以使用單詞列表進行分解。

因此，如果輸入類似於 words = ["love", "python", "we", "programming", "language"] s = "welovepythonprogramming"，則輸出將為 True

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

  • words := 所有唯一單詞的新集合
  • 定義一個函式 rec()。這將取 i
  • 如果 i 等於 s 的大小，則
    • 返回 True
  • acc := 空字串
  • 對於從 i 到 s 大小的範圍內的 j，執行以下操作：
    • acc := acc 連線 s[j]
    • 如果 acc 存在於 words 中，則
      • 如果 rec(j + 1) 為 True，則
        • 返回 True
  • 返回 False
  • 從主方法呼叫 rec(0) 並返回結果

讓我們看看下面的實現，以便更好地理解：

示例

線上演示

class Solution:
   def solve(self, words, s):
      words = set(words)

      def rec(i=0):
         if i == len(s):
            return True
         acc = ""
         for j in range(i, len(s)):
            acc += s[j]
            if acc in words:
               if rec(j + 1):
                  return True
         return False

      return rec()
     
ob = Solution()
words = ["love", "python", "we", "programming", "language"]
s = "welovepythonprogramming"
print(ob.solve(words, s))

輸入

["love", "python", "we", "programming", "language"], "welovepythonprogramming"

輸出

True

更新於：2020年12月2日

527 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告