统计只差一个字符的子串数目
难度
- Easy
- Medium
- Hard
思路
首先考虑暴力法,看字符串长度为 100,简单估计了下感觉会超时。
然后考虑不同字符出现的位置,可能是开头(其后为连续相同串),中间(两侧为连续相同串),末尾(其前为连续相同串)。
然后……就没有然后了……
打开题解,啪啪打脸。暴力是可以通过的……
看 DP 解法,嗯,枚举不同字符,应该说想的比较接近了。
暴力法没什么说的。
DP 是说,枚举两字符串中不同的字符,用两个二维数组记录不同字符对两侧的连续相同串长度。对于一对不同字符,可以组成的符合条件的子串数量,应当为两侧连续相同串长度加一的积。
代码
暴力
class Solution: def countSubstrings(self, s: str, t: str) -> int: # 暴力,枚举 ans = 0 for i in range(len(s)): for j in range(len(t)): diff = 0 k = 0 while i + k < len(s) and j + k < len(t): if s[i + k] != t[j + k]: diff += 1 if diff == 1: ans += 1 if diff > 1: break k += 1 return ans
class Solution: def countSubstrings(self, s: str, t: str) -> int: m, n = len(s), len(t) dpl = [[0] * (n + 1) for _ in range(m + 1)] dpr = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m): for j in range(n): if s[i] == t[j]: dpl[i + 1][j + 1] = dpl[i][j] + 1 for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): if s[i] == t[j]: dpr[i][j] = dpr[i + 1][j + 1] + 1 ans = 0 for i in range(m): for j in range(n): if s[i] != t[j]: ans += (dpl[i][j] + 1) * (dpr[i + 1][j + 1] + 1) return ans
其实这里 DP 也没快多少。
Comments NOTHING