LeetCode Is Subsequence

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。]]>

Leave a Reply

Your email address will not be published. Required fields are marked *