How to find if given string is a subsequence of another given string recursively without imports?

Question

Assignment:

Write a recursive function named is_subsequence that takes two string parameters and returns True if the first string is a subsequence of the second string, but returns False otherwise. We say that string A is a subsequence of string B if you can derive A by deleting zero or more letters from B without changing the order of the remaining letters. You can assume that neither string contains upper-case letters.

You may use default arguments and/or helper functions.

Your recursive function must not: use imports. use any loops use any variables declared outside of the function. use any mutable default arguments.

What I have so far (must use this format):

def is_subsequence(strA, strB = None):
if strB == None:
   strB = []

print(is_subsequence("dog", "dodger"))

My problem:
I can't figure out how to recursively edit the string the way the assignment says by removing letters. (strB.replace("e","") doesn't work).

You could try that, but I'll give you a hint: that isn't the right approach for this assignment. — Jacob Greenfield
– Jacob Greenfield, Commented Nov 4, 2020 at 0:43

Loom · Accepted Answer · 2020-11-04 18:26:25Z

I dont know if this is allowed based on the instructions but i added an index param and was able to come up with this. (Snippet is Python)

def is_subsequence(strA, strB, index=0):
    """
    Function that determines if string A is a subsequence of string B
    :param strA: String to compare subsets to (strings are immutable)
    :param strB: Parent string to make subsets of (strings are immutable)
    :param index: number of combinations tested
    :return: True if a subsequence is found, False if index reaches maximum with none found
    """

    binary = '{:0{leng}b}'.format(index, leng=len(strB))

    if index > 2**len(strB)-1:  #If past maximum return False
        return False

    def makesub(sub="", pos=0):
        """
        Function that builds up the current subsequence being tested by using binary to choose letters
        :param sub: The currently selected letters
        :param pos: Position in binary string to compare
        :return: completed subsequence for comparing to strA
        """
        if pos > len(binary)-1: #If pos is passed the length of our binary number return the created subsequence
            return sub
        if binary[pos] == "1":  #If the pos in binary is a 1, add the letter to our sub. If it is 0 do nothing.
            sub = sub + strB[pos]

        return makesub(sub, pos + 1)    #increment pos and try again or return what the call returned

    if makesub() == strA:       #If the returned sub matches strA we found a matching subsequence, return True
        return True

    return is_subsequence(strA, strB, index + 1)    #increment index and try again or return what the call returned


print(is_subsequence("dog", "dodger"))

Collectives™ on Stack Overflow

How to find if given string is a subsequence of another given string recursively without imports?

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related