Python Subsequence of a String

Question

The exercise asks me to write a program. It wrote

"Given a string s and a string t, check if s is a subsequence of t.
For example: "ac", "abcd" => True."

So I wrote this:

def isSubsequence(s, t):
        s, t = map(list, [s, t])
        for c in t:
            if c in s:
                s.pop(0)
        return not s

It worked ok in most cases except one:

s = "rjufvjafbxnbgriwgokdgqdqewn"
t = "mjmqqjrmzkvhxlyruonekhhofpzzslupzojfuoztvzmmqvmlhgqxehojfowtrinbatjujaxekbcydldglkbxsqbbnrkhfdnpfbuaktupfftiljwpgglkjqunvithzlzpgikixqeuimmtbiskemplcvljqgvlzvnqxgedxqnznddkiujwhdefziydtquoudzxstpjjitmiimbjfgfjikkjycwgnpdxpeppsturjwkgnifinccvqzwlbmgpdaodzptyrjjkbqmgdrftfbwgimsmjpknuqtijrsnwvtytqqvookinzmkkkrkgwafohflvuedssukjgipgmypakhlckvizmqvycvbxhlljzejcaijqnfgobuhuiahtmxfzoplmmjfxtggwwxliplntkfuxjcnzcqsaagahbbneugiocexcfpszzomumfqpaiydssmihdoewahoswhlnpctjmkyufsvjlrflfiktndubnymenlmpyrhjxfdcq"

I don't know why my code didn't work on this one. So if someone knows the answer, please tell me.

Your code is testing whether every character in s is also in t in any order -- here's a simple example: isSubsequence('ab', 'acb') => True. There are easier ways of testing sequence membership in Python but since it's an exercise I'm not going to just tell you ;-) — user3456014
– user3456014, Commented Jun 27, 2020 at 15:25
@Juniktw I suggest you look at a simpler example like isSubsequence('ab', 'bb'). Your code currently returns True for that, which is obviously not the desired result... — ekhumoro
– ekhumoro, Commented Jun 27, 2020 at 15:35
Yes it worked for simple test cases but not working for the larger test case as above. — Juniktw
– Juniktw, Commented Jun 27, 2020 at 15:40
@Juniktw No, it does not work for that simple case. It should return False, since 'ab' is clearly not a subsequence of 'bb'. — ekhumoro
– ekhumoro, Commented Jun 27, 2020 at 15:44

Red · Accepted Answer · 2020-06-27 17:32:53Z

2

Here is what you can do:

def isSubsequence(s, t):
    s = list(s)
    for i,(a,b) in enumerate(zip(t,s)):
        if a != b:
            s.insert(i,'.')
    return len(t) == len(s)
    
print(isSubsequence('Apes are goo.', 'Apples are good.'))

Output:

True

Your case is that that specific s is not a subsequence of that specific t. To prove it:

def isSubsequence(s, t):
    s = list(s)
    for i,(a,b) in enumerate(zip(t,s)):
        if a != b:
            s.insert(i,'.')
    print(t)
    print(''.join(s))

s = "rjufvjafbxnbgriwgokdgqdqewn"
t = "mjmqqjrmzkvhxlyruonekhhofpzzslupzojfuoztvzmmqvmlhgqxehojfowtrinbatjujaxekbcydldglkbxsqbbnrkhfdnpfbuaktupfftiljwpgglkjqunvithzlzpgikixqeuimmtbiskemplcvljqgvlzvnqxgedxqnznddkiujwhdefziydtquoudzxstpjjitmiimbjfgfjikkjycwgnpdxpeppsturjwkgnifinccvqzwlbmgpdaodzptyrjjkbqmgdrftfbwgimsmjpknuqtijrsnwvtytqqvookinzmkkkrkgwafohflvuedssukjgipgmypakhlckvizmqvycvbxhlljzejcaijqnfgobuhuiahtmxfzoplmmjfxtggwwxliplntkfuxjcnzcqsaagahbbneugiocexcfpszzomumfqpaiydssmihdoewahoswhlnpctjmkyufsvjlrflfiktndubnymenlmpyrhjxfdcq"

isSubsequence(s, t)

Output:

mjmqqjrmzkvhxlyruonekhhofpzzslupzojfuoztvzmmqvmlhgqxehojfowtrinbatjujaxekbcydldglkbxsqbbnrkhfdnpfbuaktupfftiljwpgglkjqunvithzlzpgikixqeuimmtbiskemplcvljqgvlzvnqxgedxqnznddkiujwhdefziydtquoudzxstpjjitmiimbjfgfjikkjycwgnpdxpeppsturjwkgnifinccvqzwlbmgpdaodzptyrjjkbqmgdrftfbwgimsmjpknuqtijrsnwvtytqqvookinzmkkkrkgwafohflvuedssukjgipgmypakhlckvizmqvycvbxhlljzejcaijqnfgobuhuiahtmxfzoplmmjfxtggwwxliplntkfuxjcnzcqsaagahbbneugiocexcfpszzomumfqpaiydssmihdoewahoswhlnpctjmkyufsvjlrflfiktndubnymenlmpyrhjxfdcq
......r...........................j.u...................f...............................................................v..............................j..................................................................................................a................f..b..............................................................................x............n...b....................g....................................................................................r...i.......................wgokdgqdqewn

UPDATED to include simpler implementation given by @StevenRumbalski at the comments:

def isSubsequence(s, t, start=-1): 
    return all((start:=t.find(c, start+1)) > -1 for c in s)

edited Jun 27, 2020 at 17:32

answered Jun 27, 2020 at 15:34

Red

27.7k8 gold badges44 silver badges63 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Steven Rumbalski Over a year ago

Another simple implementation (Python 3.8+) def isSubsequence(s, t, start=0): return all((start:=t.find(c, start)) > -1 for c in s)

ekhumoro Over a year ago

@StevenRumbalski That is broken, since it will return True for isSubsequence('bb', 'abc'). See this answer for a correct implementation of the algorithm.

Steven Rumbalski Over a year ago

@ekhumoro: fixed: def isSubsequence(s, t, start=-1): return all((start:=t.find(c, start+1)) > -1 for c in s)

Dong Cao-Huu · Accepted Answer · 2020-06-27 15:51:35Z

1

I suppose the order also matters

def isSubsequence(s, t): # order matters
    s, t = list(s), list(t)
    for c in s:
        if c in t:
            c_idx = t.index(c)
            t = t[c_idx:]
        else:
            return False
    return True

edited Jun 27, 2020 at 15:51

answered Jun 27, 2020 at 15:35

Dong Cao-Huu

531 silver badge8 bronze badges

Comments

Ronie Martinez · Accepted Answer · 2020-06-27 17:08:02Z

0

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

edited Jun 27, 2020 at 17:08

answered Jun 27, 2020 at 15:34

Ronie Martinez

1,2651 gold badge10 silver badges15 bronze badges

2 Comments

ekhumoro Over a year ago

It's smpler to use str.find with a start argument. If the result is -1, return False, otherwise use result + 1 for the next start argument.

ekhumoro Over a year ago

@RonieMartinez That looks broken. You want start = -1 and start = t.find(i, start + 1), and also remove start += 1.

Collectives™ on Stack Overflow

Python Subsequence of a String

3 Answers 3

3 Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related