数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：查找相等子字符串对的数量
假设我们有两个字符串，都由小写字母组成。我们需要找到满足以下条件的四元组 (p, q, r, s) 的数量：
0 <= p <= q <= 第一个字符串的长度。
0 <= r <= s <= 第二个字符串的长度。
第一个字符串从索引 p 开始到索引 q 结束的子字符串必须等于第二个字符串从索引 r 开始到索引 s 结束的子字符串。
在所有满足上述条件的四元组中，q - r 必须是最小值。
我们需要找到此类四元组的数量。
例如，如果输入为 firstString = 'hgfn'，secondString = 'gfrt'，则输出为 2。
有两个四元组 (1, 1, 0, 0) 和 (2, 2, 1, 1) 满足条件，并且 q - r 的值为最小值。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个函数 ord()。它将接收字符 ch
- 返回 ch 的 Unicode 值
- 在主方法中执行以下操作：
- left := 一个大小为 26 的新列表，其值为无穷大
- right := 一个大小为 26 的新列表，其值为 -1
- res := 0
- mi := 无穷大
- 对于第一个字符串中的每个索引 i 和字符 ch，执行：
- left[ord(ch) - ord('a') ] := min(left[ord(ch) - ord('a') ], i)
- 对于第二个字符串中的每个索引 i 和字符 ch，执行：
- right[ord(ch) - ord('a') ] := max(right[ord(ch) - ord('a') ], i)
- 对于 i in range(0, 25)：
- 如果 left[i] 不等于 -1，则
- mi := min(mi, left[i] - right[i])
- 如果 left[i] 不等于 -1，则
- 对于 i in range(0, 25)：
- 如果 left[i] 不等于无穷大且 right[i] 不等于 -1，则
- 如果 left[i] - right[i] 等于 mi，则
- res := res + 1
- 如果 left[i] - right[i] 等于 mi，则
- 如果 left[i] 不等于无穷大且 right[i] 不等于 -1，则
- 返回 res
示例
让我们看下面的实现，以便更好地理解：
def solve(firstString, secondString):
left = [float('inf')] * 26
right = [-1] * 26
res = 0
mi = float('inf')
for i, ch in enumerate(firstString):
left[ord(ch) - ord('a')] = min(left[ord(ch) - ord('a')], i)
for i, ch in enumerate(secondString):
right[ord(ch) - ord('a')] = max(right[ord(ch) - ord('a')], i)
for i in range(26):
if left[i] != -1:
mi = min(mi, left[i] - right[i])
for i in range(26):
if left[i] != float('inf') and right[i] != -1:
if left[i] - right[i] == mi:
res += 1
return res
print(solve('hgfn', 'gfrt'))输入
'hgfn', 'gfrt'
输出
2
更新于：2021年10月7日
298 次查看
广告