Python程式：檢查最終字串是否可以使用其他兩個字串構成

假設我們有兩個字串s、t，還有一個字串r，我們需要檢查是否可以透過按順序合併s和t中的字元來得到r。

例如，如果輸入為s = "xyz"，t = "mno"，r = "xymnoz"，則輸出為True，因為xymnoz可以透過交錯xyz和mno構成。

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

  • 定義一個函式solve()。它將接收s、t、r作為引數。

  • 如果s、t和r都為空，則

    • 返回True

      • 如果r為空，則

        • 返回False

  • 如果s為空，則

    • 當t與r相同時返回true，否則返回false

  • 如果t非空，則

    • 返回s與r是否相同

  • 如果s[0]與r[0]相同，則

    • 如果solve(s[從索引1到結尾], t, r[從索引1到結尾])為true，則

      • 返回True

  • 如果t[0]與r[0]相同，則

    • 如果solve(s, t[從索引1到結尾], r[從索引1到結尾])為true，則

      • 返回True

  • 返回False

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

示例

線上演示

class Solution:
   def solve(self, s, t, r):
      if not s and not t and not r:
         return True
      if not r:
         return False
      if not s:
         return t == r
      if not t:
         return s == r
      if s[0] == r[0]:
         if self.solve(s[1:], t, r[1:]):
            return True
         if t[0] == r[0]:
            if self.solve(s, t[1:], r[1:]):
               return True
         return False
ob = Solution()
s = "xyz"
t = "mno"
r = "xymnoz"
print(ob.solve(s, t, r))

輸入

"xyz", "mno", "xymnoz"

輸出

True

更新於：2020-12-26

瀏覽量：102

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告