2565.最少得分子序列

链接：2565.最少得分子序列
难度：Hard
标签：双指针、字符串、二分查找
简介：请你返回使 t 成为 s 子序列的最小得分。

题解 1 - python

• 编辑时间：2023-02-12
• 执行用时：156ms
• 内存消耗：23.2MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def minimumScore(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        pre, suf = [0] * n, [m] * (n + 1)
        i, p = 0, 0
        while i < n and p < m:
            if s[i] == t[p]:
                p += 1
            pre[i] = p
            i += 1
        i, p = n-1, m-1
        while i >= 0 and p >= 0:
            if s[i] == t[p]:
                p -= 1
            suf[i] = p+1
            i -= 1
        res = suf[0]
        for i in range(n):
            if suf[i + 1] < pre[i]:
                return 0
            res = min(res, suf[i + 1] - pre[i])
        return res

题解 2 - cpp

• 编辑时间：2023-02-12
• 执行用时：16ms
• 内存消耗：11.2MB
• 编程语言：cpp
• 解法介绍：前后缀匹配，把s分成前后两部分进行枚举，对于每一部分尝试匹配t的前后缀的最大长度。

class Solution {
public:
    int minimumScore(string s, string t) {
        int n = s.size(), m = t.size();
        vector<int> pre(n), suf(n + 1, m);
        for (int i = 0, p = 0; i < n && p < m; i++) {
            if (s[i] == t[p]) p++;
            pre[i] = p;
        }
        for (int i = n - 1, p = m - 1; i >= 0 && p >= 0; i--) {
            if (s[i] == t[p]) p--;
            suf[i] = p + 1;
        }
        int res = suf[0];
        for (int i = 0; i < n; i++) {
            if (suf[i + 1] < pre[i]) return 0;
            res = min(res, suf[i + 1] - pre[i]);
        }
        return res;
    }
};

题解 3 - rust

• 编辑时间：2023-02-12
• 内存消耗：4.8MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn minimum_score(s: String, t: String) -> i32 {
        let (s, t) = (
            s.chars().collect::<Vec<char>>(),
            t.chars().collect::<Vec<char>>(),
        );
        let (n, m) = (s.len(), t.len());
        let (mut pre, mut suf) = (vec![0; n], vec![m; n + 1]);
        let (mut i, mut p) = (0, 0);
        while i < n && p < m {
            if s[i] == t[p] {
                p += 1;
            }
            pre[i] = p;
            i += 1;
        }
        let (mut i, mut p) = ((n - 1) as i32, (m - 1) as i32);
        while i >= 0 && p >= 0 {
            if s[i as usize] == t[p as usize] {
                p -= 1;
            }
            suf[i as usize] = p as usize + 1;
            i -= 1;
        }
        let mut res = suf[0];
        for i in 0..n {
            if suf[i + 1] < pre[i] {
                return 0;
            }
            res = res.min(suf[i + 1] - pre[i]);
        }
        res as i32
    }
}