classSolution: defminimumScore(self, s: str, t: str) -> int: n, m = len(s), len(t) suf = [m] * (n + 1) j = m - 1 for i inrange(n - 1, -1, -1): if j >= 0and s[i] == t[j]: j -= 1 suf[i] = j + 1 ans = suf[0] # 删除 t[:suf[0]] if ans == 0: return0
j = 0 for i, c inenumerate(s): if c == t[j]: # 注意 j 不会等于 m,因为上面 suf[0]>0 表示 t 不是 s 的子序列 j += 1 ans = min(ans, suf[i + 1] - j) # 删除 t[j:suf[i+1]] return ans
[sol1-Java]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution { publicintminimumScore(String S, String T) { char[] s = S.toCharArray(), t = T.toCharArray(); intn= s.length, m = t.length; varsuf=newint[n + 1]; suf[n] = m; for (inti= n - 1, j = m - 1; i >= 0; --i) { if (j >= 0 && s[i] == t[j]) --j; suf[i] = j + 1; } intans= suf[0]; // 删除 t[:suf[0]] if (ans == 0) return0; for (inti=0, j = 0; i < n; ++i) if (s[i] == t[j]) // 注意 j 不会等于 m,因为上面 suf[0]>0 表示 t 不是 s 的子序列 ans = Math.min(ans, suf[i + 1] - ++j); // ++j 后,删除 t[j:suf[i+1]] return ans; } }
[sol1-C++]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution { public: intminimumScore(string s, string t){ int n = s.length(), m = t.length(), suf[n + 1]; suf[n] = m; for (int i = n - 1, j = m - 1; i >= 0; --i) { if (j >= 0 && s[i] == t[j]) --j; suf[i] = j + 1; } int ans = suf[0]; // 删除 t[:suf[0]] if (ans == 0) return0; for (int i = 0, j = 0; i < n; ++i) if (s[i] == t[j]) // 注意 j 不会等于 m,因为上面 suf[0]>0 表示 t 不是 s 的子序列 ans = min(ans, suf[i + 1] - ++j); // ++j 后,删除 t[j:suf[i+1]] return ans; } };