[LeetCode]Is Subsequence

题目描述:

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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