class Solution {
public:
int minimumScore(string s, string t) {
}
};
6357. 最少得分子序列
给你两个字符串 s 和 t 。
你可以从字符串 t 中删除任意数目的字符。
如果没有从字符串 t 中删除字符，那么得分为 0 ，否则：
left 为删除字符中的最小下标。right 为删除字符中的最大下标。字符串的得分为 right - left + 1 。
请你返回使 t 成为 s 子序列的最小得分。
一个字符串的 子序列 是从原字符串中删除一些字符后（也可以一个也不删除），剩余字符不改变顺序得到的字符串。（比方说 "ace" 是 "abcde" 的子序列，但是 "aec" 不是）。
示例 1：
输入：s = "abacaba", t = "bzaa" 输出：1 解释：这个例子中，我们删除下标 1 处的字符 "z" （下标从 0 开始）。 字符串 t 变为 "baa" ，它是字符串 "abacaba" 的子序列，得分为 1 - 1 + 1 = 1 。 1 是能得到的最小得分。
示例 2：
输入：s = "cde", t = "xyz" 输出：3 解释：这个例子中，我们将下标为 0， 1 和 2 处的字符 "x" ，"y" 和 "z" 删除（下标从 0 开始）。 字符串变成 "" ，它是字符串 "cde" 的子序列，得分为 2 - 0 + 1 = 3 。 3 是能得到的最小得分。
提示：
1 <= s.length, t.length <= 105s 和 t 都只包含小写英文字母。
原站题解
java 解法, 执行用时: 2 ms, 内存消耗: 42.1 MB, 提交时间: 2023-02-13 10:47:12
class Solution {
public int minimumScore(String S, String T) {
char[] s = S.toCharArray(), t = T.toCharArray();
int n = s.length, m = t.length;
var suf = new int[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) return 0;
for (int i = 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;
}
}
golang 解法, 执行用时: 8 ms, 内存消耗: 6 MB, 提交时间: 2023-02-13 10:46:27
func minimumScore(s, t string) int {
n, m := len(s), len(t)
suf := make([]int, n+1)
suf[n] = m
for i, j := n-1, m-1; i >= 0; i-- {
if j >= 0 && s[i] == t[j] {
j--
}
suf[i] = j + 1
}
ans := suf[0] // 删除 t[:suf[0]]
if ans == 0 {
return 0
}
for i, j := 0, 0; i < n; i++ {
if s[i] == t[j] { // 注意 j 不会等于 m，因为上面 suf[0]>0 表示 t 不是 s 的子序列
j++
ans = min(ans, suf[i+1]-j) // 删除 t[j:suf[i+1]]
}
}
return ans
}
func min(a, b int) int { if b < a { return b }; return a }
python3 解法, 执行用时: 112 ms, 内存消耗: 19.2 MB, 提交时间: 2023-02-13 10:45:52
class Solution:
def minimumScore(self, s: str, t: str) -> int:
n, m = len(s), len(t)
suf = [m] * (n + 1)
j = m - 1
for i in range(n - 1, -1, -1):
if j >= 0 and s[i] == t[j]:
j -= 1
suf[i] = j + 1
ans = suf[0] # 删除 t[:suf[0]]
if ans == 0: return 0
j = 0
for i, c in enumerate(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