题目描述
给我们两个字符串，问我们第一个字符串是否是第二个字符串的子序列。
样例
Example 1:
s = "abc", t = "ahbgdc"
Return true.

Example 2:
s = "axc", t = "ahbgdc"
Return false.
解题思路

参考程序

参考程序

这道题目需要判断第一个是否为第二个字符串的子序列。
这里我们可以用到双指针移动的方法。以 i 作为第一个字符串 s 的指针，j 为第二个字符串 t 的指针。
一开始 i 和 j 都指向字符串的开头，然后每一次我们都将j往后移动一个单位，然后判断 s[i] 是否和 t[j] 相等，如果相等我们就将 i 往后移动一个单位。
这样如果最后 i 能移动到 s 的最后一位，那么说明 s 是 t 的子序列，否则不是，因为我们每一步都在检查是否有重复都子序列，指针 j 会检查 t 里面所有可能出现在 s 里面的子序列。总共复杂度为 O(s.length + t.length)。
参考程序
1. java 版本
2. c++ 版本
3. python 版本
面试官角度分析
这道题就是简单的两个指针问题考察，能够快速想到双指针并且能够正确估算出时间复杂度，那么此题就可以得到 hire 的评价。
题目答案链接
http://www.jiuzhang.com/solutions/is-subsequence/
相关题目
Hard:  
http://www.lintcode.com/problem/edit-distance/
Hard:  
http://www.lintcode.com/problem/distinct-subsequences/
推荐阅读
《九章算法班》
《系统设计班》
《Big Data 项目实战班》
《Java入门与基础算法班》
《算法强化班》
正在报名中！
报名登陆官网 www.jiuzhang.com
或点击文末“阅读原文”
九章算法版权所有，谢绝转载。
继续阅读
阅读原文