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

开启你的职业生涯

完成课程获得认证

开始学习
广告