Python程序：统计字符差异仅为一个的子字符串

假设我们有两个字符串 s 和 t，我们需要找到从 s 中选择一个非空子字符串，并将其中的一个字符替换成另一个不同字符，使得替换后的子字符串成为 t 的一个子字符串的方法数。我们需要找到满足上述条件的子字符串数量。

例如，如果输入为 s = "sts" t = "tsts"，则输出为 6，因为以下是从 s 和 t 中选择的子字符串对，它们只有一个字符不同：

  • ("sts", "tsts"),
  • ("sts", "tsts"),
  • ("sts", "tsts"),
  • ("sts", "tsts"),
  • ("sts", "tsts"),
  • ("sts", "tsts")

加粗的部分是分别从两个字符串 s 和 t 中选择的子字符串。

为了解决这个问题，我们将遵循以下步骤：

  • n1 := s 的长度
  • n2 := t 的长度
  • ans := 0
  • 对于 s 中的每个索引 i1 和字符 c1：
    • 对于 t 中的每个索引 i2 和字符 c2：
      • i := i1，j := i2
      • 当 i < n1 且 j < n2 且 s[i] 等于 t[j] 时：
        • i := i + 1，j := j + 1
      • 如果 i < n1 且 j < n2 且 s[i] 不等于 t[j]，则
        • i := i + 1，j := j + 1
        • ans := ans + 1
        • 当 i < n1 且 j < n2 且 s[i] 等于 t[j] 时：
          • i := i + 1，j := j + 1
          • ans := ans + 1
  • 返回 ans

示例

让我们看看下面的实现以更好地理解：

def solve(s, t):
   n1 = len(s)
   n2 = len(t)
   ans = 0

   for i1, c1 in enumerate(s):
      for i2, c2 in enumerate(t):
         i = i1
         j = i2

         while i < n1 and j < n2 and s[i] == t[j]:
            i += 1
            j += 1

         if i < n1 and j < n2 and s[i] != t[j]:
            i += 1
            j += 1
            ans += 1
            while i < n1 and j < n2 and s[i] == t[j]:
               i += 1
               j += 1
               ans += 1

   return ans

s = "sts"
t = "tsts"
print(solve(s, t))

输入

"sts", "tsts"

输出

6

更新于： 2021年10月5日

浏览量：189

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告