数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学根据给定条件检查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 次浏览
广告