2 lines Python

  • 28
    def isSubsequence(self, s, t):
        t = iter(t)
        return all(c in t for c in s)

    Just testing whether all characters in s are also in t (in order).

    Based on falsetru's code on StackOverflow which I improved a while ago, see here.

  • 6

    Elegant~ another note to take~
    here is my test:

    a = [1,2,3,4,5]
    b = iter(a)
    print 1 in b #True
    print b.next() #2
    print 1 in b #False
    print b.next() #StopIteration 

    and here is my original solution...

    class Solution(object):
        def isSubsequence(self, s, t):
            start = 0
            for i in range(len(s)):
                start = t.find(s[i],start)
                if start==-1:
                    return False
                start += 1
            return True

  • 0
    This post is deleted!

  • 1

    @StefanPochmann Do we need any improvement for the follow-up question? Thanks!

  • 3

    Just curious, will use of "iter" "all" built in of Python considered a good solution during interview? Or interviewers are expected to write out the "iter" procedure?

  • 0

    you can check some primitive cases in advance

        if len(s) == len(t):
            return s == t
        if not s:
            return True
        if len(s) > len(t):
            return False

  • 2

    @xiaoyudeng666 The not s case is a bit pointless, in the rare case it saves something it saves almost nothing, but it costs a little extra all the time. Plus it's more code and I find it misleading (to me, something like that suggests that it helps prevent a weakness in the rest of the code, which is not the case here). The other two cases could be combined as if len(s) >= len(t): return s == t, I'm pretty sure Python's == implementation will compare the lengths first and thus handle the len(s) > len(t) case right away.

  • 1

    @Yu.Nicolas I'm not an interviewer so I don't know for sure, but in my opinion it doesn't exactly demonstrate mastery of the language or of concepts if I unpythonically reimplement those wheels instead of just properly using them.

  • 1

    Oh. Thank you so much. I always learn a lot from you.

  • 2

    This code is super short/fast but so hard to understand as a new python programmer. Here is an explanation for other Python newbies:

    First, we turned t into a iterator, and what that does is that "c in it" iterates through the iterator until the first position where it finds a match. See here.
    Second, (c in it for c in s) is a generator: it returns an iterator. More about generator here.
    Third, all() has only 1 parenthesis, so syntactic sugar: no need for double parentheses
    all() takes in an iterator as an argument and loops through to find the first False. If it can't find it, it return True. More about all/any and generator here.

  • 0

    Hi! I expanded the above code for easier reading:
    The idea is the same: If curr char is not in t, then we return False
    Else, we take the substring of t and start from there

    def isSubsequence(self, s, t):
        for c in s:
            i = t.find(c)
            if i == -1:
                return False
                t = t[i+1:]
        return True

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.