作者推荐
本文涉及的基础知识点
二分查找算法合集 有序向量的二分查找，初始化完成后，向量不会修改。
双指针： 用于计算子字符串是s的字符串的子系列。
题目
给你两个字符串 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 <= 105
s 和 t 都只包含小写英文字母。
分析
时间复杂度😮(nlogn)。枚举tRight，时间复杂度O(n);二分查找tLeft，时间复杂度O(logn)。令m_c是t的长度。tLeft=left-1,tRight=right+1。
变量解析
| vLeft[i]=x | 表示t[0,i]是s[0,x]子序列,x如果有多个值取最小值。如果x不存在，为任意大于等于m_c的值。显然是升序。 |
| vRight[i]=x | 表示t[t…)是s[x,…)子序列，如果x有多个值取最大值。如果x不存在，为任意小于0的值。 |
原理
将left和right直接的元素全部删除，积分不会增加，所以全删除。全删除后，只有两种情况：一，不删除。二，删除一处。t由两个部分组成。[0,tLeft]和[tRight,m_c)。如果左边为空,tLeft为-1;如果右边为空，tRight为m_c。sRight 为vRight[tRight]，sLeft是小于sRight中的最大值。这样确保[0,sLeft]和[sRight…)没有重叠部分。sLeft在vLeft中的下标就是tLeft，tLeft必须小于tRight，否则[0,tLeft]和[tRight,m_c)会有重叠部分。
特殊情况
右边为空，在初始化vRight的时候，需要特殊处理，后续操作不需要。
如果vRight[tRight]非法，需要忽略。
tLeft为-1，不需特殊处理，就是左边为空。
代码
核心代码
class Solution { public: int minimumScore(string s, string t) { m_c = t.length(); //vLeft[i]=x，表示t[0,i]是s[0,x]子序列,x如果有多个值取最小值。如果x不存在，为任意大于等于m_c的值 //vRight[i]=x，表示t[t...)是s[x,...)子序列，如果x有多个值取最大值。如果x不存在，为任意小于0的值。 vector<int> vLeft(m_c, m_c),vRight(m_c,-1); { for (int i = 0, right=0; i < m_c; i++) { while ((right < s.length()) && (s[right] != t[i])) { right++; } vLeft[i] = right++; } } { for (int i = m_c - 1,left=s.length()-1; i >= 0; i--) { while ((left >= 0) && (s[left] != t[i])) { left--; } vRight[i] = left--; } } int iRet = m_c; vRight.emplace_back(s.length());//(right,m_c)为空不需要做特殊处理 for (int tRight = 0 ; tRight < vRight.size(); tRight++) { const auto& sRight = vRight[tRight]; if (sRight < 0) { continue; } //寻找第一个小于vRight[right]的索引 int tLeft = std::lower_bound(vLeft.begin(), vLeft.end(), sRight)- vLeft.begin()-1; tLeft = min(tLeft, tRight - 1); iRet = min(iRet, tRight - tLeft - 1); } return iRet; } int m_c; };
测试用例
template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { string s, t; { Solution slu; s = "abacaba", t = "bzaa"; auto res = slu.minimumScore(s, t); Assert(1, res); } { Solution slu; s = "cde", t = "xyz"; auto res = slu.minimumScore(s, t); Assert(3, res); } { Solution slu; s = "adebddaccdcabaade", t = "adbae"; auto res = slu.minimumScore(s, t); Assert(0, res); } { Solution slu; s = "eceecbabe", t = "bdeaec"; auto res = slu.minimumScore(s, t); Assert(4, res); } //CConsole::Out(res); }
优化
第二轮循环，可以和第三轮循环合并，且改成双指针。可以直接用栈（向量）的出栈代替指针。第一轮寻找改成枚举s，更方便。
class Solution { public: int minimumScore(string s, string t) { m_c = t.length(); vector<int> vLeft; for (int is = 0; is < s.length(); is++) { if ((vLeft.size() < m_c) && (s[is] == t[vLeft.size()])) { vLeft.emplace_back(is); } } int iRet = m_c - vLeft.size(); //tRight==m_c for (int tRight = m_c - 1,sRight = s.length()-1 ; tRight >= 0; tRight--) { while ((sRight >= 0) && (s[sRight] != t[tRight])) { sRight--; } if (sRight < 0) { break; } while (vLeft.size() &&((vLeft.back() >= sRight) || (vLeft.size() > tRight))) { vLeft.pop_back(); } iRet = min(iRet, tRight - (int)vLeft.size()); sRight--; } return iRet; } int m_c; };
2023年3月旧代码
class Solution { public: int minimumScore(string s, string t) { m_c = t.length(); m_c2 = s.length(); m_vLeft.assign(m_c, m_c2); m_vRight.assign(m_c, -1); { int j = 0; for (int i = 0; i < m_c; i++) { while ((j < m_c2) && (s[j] != t[i])) { j++; } if (s.length() == j) { break; } m_vLeft[i] = j++; } } { int j = s.length()-1 ; for (int i = m_c - 1; i >= 0; i–) { while ((j >= 0 ) && (s[j] != t[i])) { j–; } if (-1 == j) { break; } m_vRight[i] = j–; } } int left = -1, right = m_c; for (; left + 1 != right;) { const int len = (left + right) / 2; if (Can(len)) { right = len; } else { left = len; } } return right; } bool Can(int len) { for (int i = 0; i + len - 1 < m_c; i++) { bool bCan = true; if (i + len == m_c) { bCan = m_vLeft[i - 1] < m_c2; } else if (0 == i) { bCan = m_vRight[i + len] > -1; } else { bCan = m_vLeft[i - 1] < m_vRight[i + len]; } if (bCan) { return true; } } return false; } vector m_vLeft, m_vRight; int m_c; int m_c2; };
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
