Lintcode392 Is Subsequence solution 题解
发布在刷题能手——Lintcode 题解2018年4月3日view:313
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace”is a subsequence of “abcde” while “aec” is not).

给定一个字符串s和一个字符串t,检查s是否是t的子序列。

可以认为,你可以假设在s和t中只有小写的英文字母。t是一个长(长度~ = 500,000)的字符串,s是一个短字符串(< = 100)。

一个字符串的子序列是一个新的字符串,它是由原来的字符串通过删除一些字符而形成的,而不影响其余字符的相对位置。(即“ace”是“abcde”的子序列,而“aec”则不是)。

【题目链接】

www.lintcode.com/en/problem/is-subsequence/

【题目解析】

      首先想到的方法是,使用两个队列分别保存两个字符串中的各个字符,依次比较队首元素,若两个队列的队首元素相同,则表示到目前为止,s的前x个字符可以匹配为t的子序列;如果两个队列的队首元素不相同,则将t队列的首元素出队列,继续比较…….

       当两个队列中有一个队列为空时,上述比较结束,此时判断s队列是否为空,若为空表示s的各个字符都匹配到了t中的字符,因此s是t的子序列;若s队列不为空,表示s字符串中有某些字符没有办法和t字符串无法匹配,因此s不是t的子序列。

【参考答案】

www.jiuzhang.com/solutions/is-subsequence/

者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN
刷题能手——Lintcode 题解

日常更新算法刷题~

我的收藏