本文涉及知识点

C++贪心 决策包容性

LeetCode3302. 字典序最小的合法序列

给你两个字符串 word1 和 word2 。
如果一个字符串 x 修改 至多 一个字符会变成 y ，那么我们称它与 y 几乎相等 。
如果一个下标序列 seq 满足以下条件，我们称它是 合法的 ：
下标序列是 升序 的。
将 word1 中这些下标对应的字符 按顺序 连接，得到一个与 word2 几乎相等 的字符串。
请你返回一个长度为 word2.length 的数组，表示一个
字典序最小
的 合法 下标序列。如果不存在这样的序列，请你返回一个 空 数组。
注意 ，答案数组必须是字典序最小的下标数组，而 不是 由这些下标连接形成的字符串。
示例 1：
输入：word1 = “vbcca”, word2 = “abc”
输出：[0,1,2]
解释：
字典序最小的合法下标序列为 [0, 1, 2] ：
将 word1[0] 变为 ‘a’ 。
word1[1] 已经是 ‘b’ 。
word1[2] 已经是 ‘c’ 。
示例 2：
输入：word1 = “bacdc”, word2 = “abc”
输出：[1,2,4]
解释：
字典序最小的合法下标序列为 [1, 2, 4] ：
word1[1] 已经是 ‘a’ 。
将 word1[2] 变为 ‘b’ 。
word1[4] 已经是 ‘c’ 。
示例 3：
输入：word1 = “aaaaaa”, word2 = “aaabc”
输出：[]
解释：
没有合法的下标序列。
示例 4：
输入：word1 = “abc”, word2 = “ab”
输出：[0,1]
提示：
1 <= word2.length < word1.length <= 3 * 10⁵
word1 和 word2 只包含小写英文字母。

贪心之决策包容性

令s = word1,t = word2。N =s.length M = t.length

情况简化，如果x不能改变一个字符

如果t[0]和s多个字符匹配，则一定匹配下标最小的，否则更换之也是解。且字典序更小。删除已匹配内容，不断迭代。

本题难度：如何分配唯一的改变机会

如果相等，改变不改变效果一样，故不改变。可以节省改变机会。
如果不等，且改变后余下字符能匹配，则改变。这样字典序最小。
suff[i]=j 表示t长度为i+1的后缀，可以和s长度为j+1的后缀匹配，切j最小。将s和t转置后，可以转成前缀问题。
suff(M,N);
for(i=0,j=0; (i < M ) && ( j < N) ; )
if(trev[i] == srev[j] ) suff[i]=j, i++,j++
else j++

主函数

b = 1
for(int i = 0 ,j=0; (i<M)&&(j < N); j++ )
如果t[i] == s[j] 则ans.Add(j) i++,j++
如果能使用改变, 则ans.Add(j) b =0 ,i++,j++
否则：j++
return i >= M

能使用改变逻辑

同是满足以下条件：
一，b > 0
二，i1 = M-j-1-1
或i1 < 0或 suff(i1)+1 <= N-i-1

代码

核心代码

class Solution {
		public:
			vector<int> validSequence(string word1, string word2) {
				const int N = word1.length(), M = word2.size();
				auto Suff = [&](const string& s, const string& t) {
					vector<int> suff(M, N);
					int i = 0;
					for (int j = 0; (i < M) && (j < N);) {
						if (t[i] == s[j]) { suff[i] = j; i++; j++; }
						else { j++; }
					}
					return suff;
				};
				auto suff = Suff(string(word1.rbegin(), word1.rend()), string(word2.rbegin(), word2.rend()));
				vector<int> ans;
				int b = 1;
				for (int i=0,j = 0; (i < M) && (j < N);) {
					if (word2[i] == word1[j]) { ans.emplace_back(j); i++; j++; }
					else { 
						const int i1 = M - i - 1 - 1;
						if (b && ((i1< 0)|| (suff[i1] + 1 <= N - j - 1))) {
							b--;
							ans.emplace_back(j); i++; j++;
						}
						else {
							j++;
						}
					}
				}
				return (ans.size() < M) ? vector<int>{} : ans;
			}
			
		};

单元测试

string word1, word2;
		TEST_METHOD(TestMethod11)
		{
			word1 = "vbcca", word2 = "abc";
			auto res = Solution().validSequence(word1, word2);
			AssertEx({ 0,1,2 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			word1 = "bacdc", word2 = "abc";
			auto res = Solution().validSequence(word1, word2);
			AssertEx({ 1,2,4 }, res);
		}
		TEST_METHOD(TestMethod13)
		{
			word1 = "aaaaaa", word2 = "aaabc";
			auto res = Solution().validSequence(word1, word2);
			AssertEx({  }, res);
		}
		TEST_METHOD(TestMethod14)
		{
			word1 = "abc", word2 = "ab";
			auto res = Solution().validSequence(word1, word2);
			AssertEx({ 0,1 }, res);
		}
		TEST_METHOD(TestMethod15)
		{
			word1 = "ccbccccbcc", word2 = "b";
			auto res = Solution().validSequence(word1, word2);
			AssertEx({ 0 }, res);
		}