LeetCode 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的子串，则s必须是t中连续的一段；而如果是子序列的话，则s只需要是t中若干个字符，但这些字符顺序必须和t中的一样。 比如t=”abcdefghijk”，则”cdef”既可以是t的子串，也可以是t的子序列；而”bfjk”只能是t的子序列。 本题很简单，维护两个指针i,j，分别指向s和t，从t中不断找字符s[i]，没找到只递增j，找到的话同时递增i和j。如果最后i到达s的末尾了，说明s是t的子序列，否则不是。 代码如下： [cpp] class Solution { public: bool isSubsequence(string s, string t) { int m = s.size(), n = t.size(); if (m > n)return false; int i = 0, j = 0; while (i < m&&j < n) { while (j < n&&s[i] != t[j])++j; if (j >= n)return false; ++i; ++j; } return i == m; } }; [/cpp] 本代码提交AC，用时73MS。]]>