Python程序：通过移除首尾元素并重新插入创建目标字符串

假设我们有两个字符串 S 和 T，它们互为排列。假设存在一个操作，其中我们移除 S 的第一个或最后一个字符，并将其插入字符串中的任何位置。然后找到将 S 转换为 T 所需的最少操作次数。

因此，如果输入类似于 s = "zyvxw" t = "vwxyz"，则输出将为 3，因为这些操作为：移除 "w" 并将其插入 "v" 后面得到 "zyvwx"，移除 "z" 并将其插入 "x" 后面得到 "yvwxz"，移除 "y" 并将其插入 "x" 后面得到 "vwxyz"。

为了解决这个问题，我们将遵循以下步骤：

• ans := s 的大小，n := s 的大小

• 对于 i 从 0 到 n-1，执行以下操作

  • k := 0

  • 对于 j 从 i 到 n-1，执行以下操作

    • 对于 k 从 k 到 t 的大小，执行以下操作

      • 如果 s[j] 等于 t[k]，则

        • ans := ans 和 n - (j - i + 1) 的最小值

        • 退出循环

    • k := k + 1

  • 返回 ans

让我们看看以下实现，以便更好地理解：

示例

 在线演示

class Solution:
   def solve(self, s, t):
      ans = n = len(s)

      for i in range(n):
         k = 0
         for j in range(i, n):
            for k in range(k, len(t)):
               if s[j] == t[k]:
                  ans = min(ans, n - (j - i + 1))
                  break
            k += 1

      return ans

ob = Solution()
s = "zyvxw"
t = "vwxyz"
print(ob.solve(s, t))

输入

"zyvxw", "vwxyz"

输出

5

Arnab Chakraborty

更新于： 2020年10月7日

91 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习