题目描述：

LeetCode 392. 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.

题目大意：

给定字符串s与字符串t，判断s是否是t的子序列。

你可以假设两字符串中都只包含小写字母。t的长度可能会很长（长度 ~= 500,000），s长度较短（<=100）

某字符串的子序列是指从其中删除某些字母（也可以不删除），而剩余字符的相对顺序保持不变，得到的新字符串。（例如，"ace"是"abcde"的子序列，而"aec"则不是）。

解题思路：

利用队列（Queue）数据结构。

将s加入队列，遍历t，当t的当前字符c与队头相同时，将队头弹出。

最后判断队列是否为空即可。

Python代码：

class Solution(object):
    def isSubsequence(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        queue = collections.deque(s)
        for c in t:
            if not queue: return True
            if c == queue[0]:
                queue.popleft()
        return not queue

 

本文链接：http://bookshadow.com/weblog/2016/09/04/leetcode-is-subsequence/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码