DEV Community
·
LeetCode 挑战：392. 是否为子序列 - JavaScript 解法 🚀
💡
原文英文，约700词，阅读约需3分钟。
📝
内容提要
Subsequence问题要求判断字符串s是否为字符串t的子序列。可以使用双指针法遍历两个字符串，或通过预处理t构建字符索引以加速查找。时间复杂度为O(n+m)或O(n·logm)。
🎯
关键要点
- Subsequence问题要求判断字符串s是否为字符串t的子序列。
- 子序列是通过删除原字符串中的某些字符（或不删除）而不改变剩余字符的相对顺序形成的。
- 使用双指针法遍历两个字符串，检查s中的字符是否按顺序出现在t中。
- 时间复杂度为O(n+m)，空间复杂度为O(1)。
- 如果有多个s字符串需要检查，可以预处理t以加速查找。
- 预处理t为字符位置的映射，允许使用二分查找快速定位s中每个字符的下一个有效位置。
- 预处理时间复杂度为O(m)，查询时间复杂度为O(n·logm)。
- 双指针法适合单个查询，预处理更适合多个查询。
- 讨论边界情况：空字符串s总是返回true，s中的字符不在t中总是返回false。
- 预处理可以减少冗余计算，提高效率。
❓
延伸问答
什么是子序列？
子序列是通过删除原字符串中的某些字符（或不删除）而不改变剩余字符的相对顺序形成的。
如何判断字符串s是否为字符串t的子序列？
可以使用双指针法遍历两个字符串，检查s中的字符是否按顺序出现在t中。
双指针法的时间复杂度是多少？
时间复杂度为O(n+m)，其中n是s的长度，m是t的长度。
如果有多个s字符串需要检查，应该如何处理？
可以预处理t为字符位置的映射，以加速查找，使用二分查找快速定位s中每个字符的下一个有效位置。
预处理t的时间复杂度和空间复杂度是多少？
预处理时间复杂度为O(m)，空间复杂度为O(m)。
空字符串s的情况如何处理？
空字符串s总是返回true。
➡️
