使用 Python 將兩個字串拆分為迴文

假設我們有兩個長度相同的字串 a 和 b。我們需要選擇一個索引並將這兩個字串在該索引處拆分，將 a 拆分為兩個字串：a_pref 和 a_suff，其中 a = a_pref | a_suff，並將 b 拆分為兩個字串：b_pref | b_suff（| 是連線運算子），其中 b = b_pref + b_suff。檢查 a_pref + b_suff 或 b_pref + a_suff 是否形成迴文。（任何拆分都可以是空字串）

因此，如果輸入類似於 a = "pqrst" b = "turqp"，則輸出將為 True，因為我們可以將 a 拆分為 ["pq", "rst"]，並將 b 拆分為 ["tu", "rqp"]，因此如果我們將 a_pref 與 b_suff 連線起來，我們將得到 "pqrqp"，這是一個迴文。

為了解決這個問題，我們將遵循以下步驟 -

• 對於來自配對列表 [(a, b), (b, a)] 的每個配對 (x, y)，執行以下操作

  • i := 0, j := x 的大小 - 1

  • 當 x[i] 與 y[j] 相同且 i < x 的大小且 j > 0 時，執行以下操作

    • i := i + 1

    • j := j - 1

  • midx := 從索引 i 到 j 的 x 的子字串

  • midy := 從索引 i 到 j 的 y 的子字串

  • 如果 midx 是迴文或 midy 是迴文，則

    • 返回 True

• 返回 False

示例

讓我們看看以下實現以更好地理解 -

def solve(a, b):
   for x, y in [[a, b], [b, a]]:
      i, j = 0, len(x) - 1
      while x[i] == y[j] and i<len(x) and j>0:
         i += 1
         j -= 1
      midx = x[i:j+1]
      midy = y[i:j+1]
      if (midx == midx[::-1] or midy== midy[::-1]):
         return True
   return False

a = "pqrst"
b = "turqp"
print(solve(a, b))

輸入

"pqrst", "turqp"

輸出

True

Arnab Chakraborty

更新於: 2021 年 10 月 5 日

666 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始學習