在 Python 中,找到索引 i,使得 S1 的前缀和 S2 的后缀直到 i 连接在一起时形成回文

pythonserver side programmingprogramming更新于 2025/10/10 11:24:17

假设我们有两个长度相同的字符串 S1 和 S2,我们必须找到一个索引 i,使得 S1[0…i] 和 S2[i+1…n-1] 连接在一起时形成回文。如果不可能,则返回 -1。

因此,如果输入为 S1 = "pqrsu", S2 = "wxyqp",则输出将为 1,因为 S1[0..1] = "pq", S2[2..n-1] = "ypq",然后 S1 + S2 = "pqyqp"表示是回文。

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

  • n := str1 的大小

  • str := 空字符串

  • 对于范围从 0 到 n 的 i,执行

    • str := str concatenate str1[i]

    • temp := 空字符串

    • 对于范围从 i + 1 到 n 的 j,执行

      • temp := temp concatenate str2[j]

    • 如果 isPalindrome(str concatenate temp) 为真,则

      • 返回 i

  • 返回 -1

示例

让我们看看下面的实现以便更好地理解 −

def isPalindrome(s):
   if s == s[::-1]:
      return True
   return False
def find_index(str1, str2):
   n = len(str1)
   str = ""
   for i in range(n):
      str = str + str1[i]
      temp = ""
      for j in range(i + 1, n):
         temp += str2[j]
      if (isPalindrome(str + temp)):
         return i
   return -1
str1 = "pqrsu"
str2 = "wxyqp"
print(find_index(str1, str2))

输入

"pqrsu", "wxyqp"

输出

1

相关文章


有用资源