用 Python 中的等效对检查字符串是否为回文的程序
假设我们有一个名为s的小写字母字符串，还有一个名为“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"]]，那么输出将是真的，因为“a”=“k”，而“r”=“t”所以字符串可以是回文的“racecar”。
示例
让我们看看以下实现以获得更好的理解-
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