计算Python中相差一个字符的子字符串的程序

假设我们有两个字符串 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 中选择的子字符串。

示例

让我们看看以下实现以获得更好的理解 -

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