使用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：其中列表不包含重复元素的图的邻接列表
  • 对于pairs中的每个x，y，请执行以下操作 –
  • 将x插入到g [x]的末尾
  • 将y插入到g[y]的末尾
  • 将y插入到g[x]的末尾
  • 将x插入到g[y]的末尾
• 定义一个函数dfs()。这将需要a，so_far
• 将a插入到so_far中
• 对于g [a]中的每个元素，请执行以下操作 –
  • 如果elem不在so_far中，则
    • dfs(elem，so_far)
• 从主方法开始，进行以下操作 –
• 对于g的每个键，请执行以下操作 –
  • dfs(key，G [key])
  • 对于i在范围0到floor of(size of s / 2)，执行以下操作
    • 如果s [i]与s [size of s-1-i]相同或(s [i]在G [s [size of 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