字符串的 子序列 是从原始字符串中生成的新字符串,可以从中删去一些字符(可以是""),而不改变其余字符的相对顺序。
朴素判定某个字符串是为另一字符串的子序列的复杂度为 ,对于本题共有 个字符串需要判定,每个字符串最多长为 ,因此整体计算量为 ,会超时。
不可避免的是,我们要对每个 进行检查,因此优化的思路可放在如何优化单个 的判定操作。
朴素的判定过程需要使用双指针扫描两个字符串,其中对于原串的扫描,会有大量的字符会被跳过(无效匹配),即只有两指针对应的字符相同时,匹配串指针才会后移。
我们考虑如何优化这部分无效匹配。
对于任意一个 而言,假设我们当前匹配到 位置,此时我们已经明确下一个待匹配的字符为 ,因此我们可以直接在 s 中字符为 的位置中找候选。
具体的,我们可以使用哈希表 map 对 s 进行预处理:以字符 为哈希表的 key,对应的下标 集合为 value,由于我们从前往后处理 s 进行预处理,因此对于所有的 value 均满足递增性质。
❝
最后考虑如何判定某个 是否满足要求:待匹配字符串 w 长度为 m,我们从前往后对 w 进行判定,假设当前判待匹配位置为 ,我们使用变量 idx 代表能够满足匹配 的最小下标(贪心思路)。
空间复杂度:
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的“笔试/面试”相关资料可访问排版精美的 合集新基地 🎉🎉