使用 Python 检查字符串是否可以在 K 步内转换的程序

假设我们有两个字符串 s 和 t，我们需要检查 s 是否可以在 k 步或更少的步数内转换为 t。在第 i 步，您可以执行以下操作。

  • 在 s 中选择任何索引 j（从 1 开始），使得 1 <= j <= s 的大小，并且 j 在任何先前的移动中都没有被选择，并将该索引处的字符移动 i 次。

  • 保持不变。

这里移动字符意味着用字母表中的下一个字母替换它（如果字母是 'z'，则将其环绕到 'a'）。因此，将字符移动 i 次表示应用 i 次移动操作。

因此，如果输入类似于 s = "poput" t = "vwput" k = 9，则输出将为 True，因为在 i = 6 时，我们可以将 'p' 转换为 'v'，在 i = 8 时，我们可以将 'o' 转换为 'w'。

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

  • 如果 s 的大小与 t 的大小不同，则

    • 返回 False

  • count := 一个数组，包含所有从 0 到 25 的 i 的 (1 和 (k - i + 1 +(k - i)/26) 的最小值)

  • 对于 s 中的每个字符 c1 和 t 中的每个字符 c2，执行

    • 如果 c1 与 c2 不相同，则

      • diff :=(c2 的 ASCII 码 - c1 的 ASCII 码 + 26) 模 26

      • 如果 count[diff] <= 0，则

        • 返回 False

      • count[diff] := count[diff] - 1

  • 返回 True

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

示例

 实时演示

def solve(s, t, k):
   if len(s) != len(t):
      return False
   count = [min(1, k - i + 1) + (k - i)//26 for i in range(26)]
   for c1, c2 in zip(s, t):
      if (c1 != c2):
         diff = (ord(c2) - ord(c1) + 26) % 26
         if count[diff] <= 0:
            return False
         count[diff] -= 1
   return True
s = "poput"
t = "vwput"
k = 9
print(solve(s, t,k))

输入

"poput","vwput",9

输出

True

更新于: 2021年5月29日

152 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告