计算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