在 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

Arnab Chakraborty

更新於: 2020-08-25

134 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習