在 Python 中查找索引 i，使得 S1 的前缀和 S2 到 i 的后缀连接起来构成回文串

假设我们有两个相同长度的字符串 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 := 空字符串

  • 对于 i 从 0 到 n 的范围，执行以下操作：

    • str := str 连接 str1[i]

    • temp := 空字符串

    • 对于 j 从 i + 1 到 n 的范围，执行以下操作：

      • temp := temp 连接 str2[j]

    • 如果 isPalindrome(str 连接 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

更新于: 2020-08-25

134 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告