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])
• 对于 i in range(0, 25)：
  • 如果 left[i] 不等于无穷大且 right[i] 不等于 -1，则
    • 如果 left[i] - right[i] 等于 mi，则
      • res := res + 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

Arnab Chakraborty

更新于：2021年10月7日

298 次查看

开启您的职业生涯

完成课程后获得认证

开始