用 Python 编写一个程序，通过从第一个或最后一个字符中删除并再次插入来制作目标

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

因此，如果输入为 s = "zyvxw" t = "vwxyz"，则输出将为 3，因为这些操作是:删除 "w" 并将其插入 "v" 之后以获得 "zyvwx" 删除 "z" 并将其插入 "x" 之后以获得 "yvwxz" 删除 "y" 并将其插入 "x" 之后得到"vwxyz"。

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

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

• 对于范围在 0 到 n-1 内的 i，执行

  • k := 0

  • 对于范围在 i 到 n-1 内的 j，执行

    • 对于范围在 k 到 t 的大小内的 k，执行

      • 如果 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

相关文章

• 用 Python 编写程序，求出排序列表中每对数字的绝对差之和
• 用 Python 编写程序，查找使列表元素相等的最小总成本
• 用 Python 编写的程序，通过使用左子树和右子树本身的值来更新值，从而找到一棵树
• 用 Python 中的字符串字符计算我们可以生成的唯一回文数的程序
• 用 Python 计算顶点到顶点可达性矩阵的程序
• 用 Python 编写程序来计算投掷 n 个骰子的方法数
• 使用 C++ 对矩阵的每个对角线元素按升序排序的程序
• 用 Python 编写的程序，用于查找赢得删除重复整数游戏所需的移动次数
• 用 Python 编写一个程序，通过从第一个或最后一个字符中删除并再次插入来制作目标
• 用 Python 编写的程序，用于从二叉树中删除所有具有偶数值的叶子