[LeetCode]392. Is Subsequence 后继

题目地址:

https://leetcode.com/problems/is-subsequence/

题目描述:

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).

Example 1:
s = "abc", t = "ahbgdc"

Return true.

Example 2:
s = "axc", t = "ahbgdc"

Return false.

Follow up:
If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

题目大意:

提供一个字符串 s 和字符串 t ,检查 s 是否是 t 的后继。

你可以假设只有少量的英文字幕在 s 和 t 中。t 有成为很长的(长度≈500000)字符串,同时 s 是一个短字符串(<=100).

一个字符串的后继是来自于某个原始的字符串删除一些字符(可能没有)所得来的。除了干扰的字符串以外。(迷の翻译)(”ace”是”abcde”的后继而”aec”不是)

例子1:

s = "abc", t = "ahbgdc"

返回 true

例子2:

s = "axc", t = "ahbgdc"

返回 false.

更进一步:

如果有很多进入的 S ,叫做 S1, S2, … , Sk 同时 k >= 1B,并且你想要一个个检查 T 是不是有它的后继。在这种情况下,你该如何改你的代码?


 

好久没做,还是扛出来了。

其实这题的题目有点绕,不过看例子还是比较清晰的。不过我还是觉得这个“后继”,有点牵强了。

本题的思路为,遍历字符串,一个个匹配过去,如果 t 中有所有 s 字符串中的字符,同时其顺序与字符串 s 一致,那么 s 是 t 的后继,就返回 true。

其中,for循环的判断条件应为“与”,而非“或”。

 

那么这题前辈的算法和我挺相似的,在这里还是贴一份。

答案地址:http://www.cnblogs.com/dongling/p/5843697.html

算法分析

该问题的算法还是很简单的,直接从s和t的首端开始遍历比较字符是否相等即可,如果不等,则增加在t中的下标位置;如果相等,则同时增加在s和t中的下标位置。如果t中的指标位置增长到了t的末尾,而s中的指标还没有增长的末尾,则返回false。如果s中的指标先增长到了末尾,则返回true。