求source子序列交错拼接为target的最小数量及方法正确性验证

思路正确性验证 #

你的贪心思路是完全正确的，证明可以用交换论证：

• 假设存在一个最优解，其第一次选取的公共子序列长度为k，而你贪心选取的LCS长度为l，显然l >=k。
• 你用LCS替换最优解的第一个子序列后，剩余待匹配的target长度比最优解剩余的更短，后续需要的步数不可能超过最优解的剩余步数，因此整体步数不会比最优解大，说明贪心策略可以得到最优解。

你的代码可以正确处理样例，逻辑没有问题。

更优的求解方案 #

你当前的实现时间复杂度较高，每次求LCS的时间是O(mn)（m是source长度，n是target长度），最坏情况下需要执行O(n)次，总复杂度是O(mn²)，当n较大时会超时。
我们可以用O(n log n)的方法求解，思路基于Dilworth定理：

该问题等价于给target的每个字符分配一个source中的对应位置（同字符匹配），要求同一分组的位置严格递增，求最少分组数。根据Dilworth定理，最少分组数等于位置序列的最长严格递减子序列的长度。

具体步骤：

1. 预处理source，记录每个字符出现的所有位置，用字典存储。如果target中存在source没有的字符，直接返回-1。
2. 遍历target，构造位置序列：对于每个字符c，按顺序循环取source中c的位置，加入序列。
3. 求该序列的最长严格递减子序列的长度，就是所求的最小个数。求最长递减子序列可以转化为求反序列的最长递增子序列，用二分优化实现O(n log n)的时间复杂度。

优化后的代码示例 #

import bisect
from collections import defaultdict

class Solution:
    def shortestWay(self, s: str, t: str) -> int:
        # 预处理每个字符在source中的位置
        pos = defaultdict(list)
        for idx, c in enumerate(s):
            pos[c].append(idx)
        # 检查target是否有source不存在的字符
        for c in t:
            if c not in pos:
                return -1
        # 构造位置序列
        ptr = defaultdict(int) # 每个字符当前取到第几个位置
        seq = []
        for c in t:
            lst = pos[c]
            seq.append(lst[ptr[c]])
            ptr[c] = (ptr[c] + 1) % len(lst)
        # 求最长严格递减子序列，转化为求反序列的最长严格递增子序列
        rev_seq = [-x for x in seq]
        dp = []
        for num in rev_seq:
            idx = bisect.bisect_left(dp, num)
            if idx == len(dp):
                dp.append(num)
            else:
                dp[idx] = num
        return len(dp)

用你给出的样例测试：

• source = "adbsc"，字符位置存储为{'a':[0],'d':[1],'b':[2],'s':[3],'c':[4]}
• target = "addsbc"，构造的序列是[0,1,1,3,2,4]
• 反序列为[0,-1,-1,-3,-2,-4]，最长递增子序列长度是2，和预期输出一致。

内容的提问来源于stack exchange，提问作者GooT