根據給定條件檢查Python中兩個字串是否等價

假設我們有兩個大小相同的字串 s 和 t。我們必須檢查 s 和 t 是否等價。

  • 它們都相等。或者，
  • 如果我們將 s 分成兩個大小相同的連續子字串，子字串為 s1 和 s2，並將 t 同樣分成 t1 和 t2，則以下之一應有效：
    • s1 遞迴地等價於 t1，s2 遞迴地等價於 t2
    • s1 遞迴地等價於 t2，s2 遞迴地等價於 t1

因此，如果輸入類似於 s = "ppqp" t = "pqpp"，則輸出將為 True，因為如果我們將 s 和 t 分成兩部分 s1 = "pp"，s2 = "qp" 和 t1 = "pq"，t2 = "pp"，這裡 s1 = t2，如果我們將 s2 和 t1 分成兩部分 s21 = "q"，s22 = "p"，t11 = "p"，t12 = "q"，這裡也有 s21 = t12 和 s22 = t11，所以它們是遞迴等價的。

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

  • 定義一個函式 util()。這將接收 s。
  • 如果 s 的大小是奇數，則
    • 返回 s
  • left := util(s 的左半部分)
  • right := util(s 的右半部分)
  • 返回 (left 連線 right) 和 (right 連線 left) 的最小值
  • 在主方法中，當 util(s) 與 util(t) 相同時返回 true，否則返回 false

讓我們看看下面的實現，以便更好地理解：

示例程式碼

線上演示

def util(s):
   if len(s) & 1 != 0:
      return s
 
   left = util(s[0:int(len(s) / 2)])
   right = util(s[int(len(s) / 2):len(s)])
 
   return min(left + right, right + left)
 
def solve(s,t):
   return util(s) == util(t)

s = "ppqp"
t = "pqpp"
print(solve(s, t))

輸入

"ppqp", "pqpp"

輸出

True

更新於：2021年1月16日

330 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告