数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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)
- 如果元素不在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
- 如果s[i]与s[s的长度 -1-i]相同，或者(s[i]在G[s[s的长度 - 1-i]]中或s[-1 - i]在G[s[i]]中)，则
- 返回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 次查看
广告