用 Python 编写一个程序来计算相差一个字符的子字符串

pythonserver side programmingprogramming更新于 2025/11/30 3:56:17

假设我们有两个字符串 s 和 t，我们必须找出有多少种方法可以选择 s 的一个非空子字符串，并用另一个不同的字符替换一个字符，使得生成的子字符串是 t 的子字符串之一。我们必须找出满足上述条件的子字符串的数量。

因此，如果输入为 s = "sts" t = "tsts"，则输出将为 6，因为以下是从 s 和 t 中相差 1 个字符 − 的子字符串对。

("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 + 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))