Python程式檢查字串是否為迴文（包含等價對）

假設我們有一個名為s的小寫字母字串，還有一個名為'pairs'的配對列表。pairs中的每個元素都包含兩個字串[a, b]，其中字元'a'和'b'被認為是相同的。如果存在兩個對，例如[a, b]和[b, c]，那麼我們可以說a和b是等價的，b和c也是等價的，所以a和c也是等價的。任何值a或b都與其自身等價。我們必須檢查s是否為迴文，並考慮給定的等價關係。

因此，如果輸入類似於s = "raceckt" pairs = [["r", "t"], ["a", "k"], ["z", "x"]]，則輸出將為True，因為"a" = "k"，"r" = "t"，所以字串可以是"racecar"，這是一個迴文。

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

  • g := 圖的鄰接表，其中列表可能包含重複元素
  • G := 圖的鄰接表，其中不包含重複元素
    • 對於每個x, y in pairs，執行：
    • 將x插入到g[x]的末尾
    • 將y插入到g[y]的末尾
    • 將y插入到g[x]的末尾
    • 將x插入到g[y]的末尾
  • 定義一個函式dfs()。這將接收a, so_far
  • 將a插入到so_far
  • 對於g[a]中的每個元素，執行：
    • 如果元素不在so_far中，則
      • dfs(elem, so_far)
  • 從主方法中，執行以下操作：
  • 對於g中的每個鍵，執行：
    • dfs(key, G[key])
    • 對於i in range 0 到 floor(s的長度 / 2)，執行：
      • 如果s[i]與s[s的長度 -1-i]相同，或者(s[i]在G[s[s的長度 - 1-i]]中或s[-1 - i]在G[s[i]]中)，則
        • 進入下一個迭代
      • 否則，
        • 返回False
  • 返回True

示例

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

from collections import defaultdict
def solve(s, pairs):
   g = defaultdict(list)
   G = defaultdict(set)
   for x, y in pairs:
      g[x].append(x)
      g[y].append(y)
      g[x].append(y)
      g[y].append(x)

   def dfs(a, so_far):
      so_far.add(a)
      for elem in g[a]:
         if elem not in so_far:
            dfs(elem, so_far)

   for key in g:
      dfs(key, G[key])

   for i in range(0, len(s) // 2):
      if s[i] == s[-1 - i] or (s[i] in G[s[-1 - i]] or s[-1 - i] in G[s[i]]):
         continue
      else:
         return False
   return True

s = "raceckt"
pairs = [["r", "t"], ["a", "k"], ["z", "x"]]
print(solve(s, pairs))

輸入

"raceckt", [["r", "t"], ["a", "k"], ["z", "x"]]

輸出

True

更新於：2021年10月14日

131 次檢視

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告