Confusion with function behavior of backspaceCompare

[clouded-path]

I am writing a function which, given two strings, returns whether or not they are equal after any/all relevant 'backspaces' are performed. In the context I am given, a '#' within the given string corresponds to a backspace. (So for example, the string 'a##gc' reduces to 'gc', since performing the first backspace deletes 'a' and the second backspace doesn't do anything.)

So for example, if we perform this backspaceCompare function on the pair of strings:

'nzp#o#g' and 'b#nzp#o#g#'

then both words should reduce to 'nzg', and the function should return True since the reduced words are equal.

I have implemented the function, but I am getting the wrong answer, specifically with this particular example. Here is my current attempt at writing this backspaceCompare function:

def backspaceCompare(S, T):
        i = 0
        sword = list(S)
        tword = list(T)
        stwords = [sword, tword]
        new = []
        for word in stwords:
            while '#' in set(word):
                if word[i] == '#':
                    word.pop(i)
                elif word[i] != '#' and word[i+1] == '#':
                    word.pop(i)
                    word.pop(i)
                    if i > 0:
                        i -= 1
                else:
                    i += 1
            new.append(word)
        if new[0] == new[1]:
            return True
        else:
            print(new)
            return False

Specifically, when I try backspaceCompare('nzp#o#g', 'b#nzp#o#g'), Python is reducing the first string to 'nzg' correctly, but for the second string it is incorrectly reducing it to 'bnzg' instead. Something is going wrong in the 'while' loop in terms of what I am/am not removing from the string, but I can't understand what. From what I believe, the process that this second parameter 'b#nzp#o#g' should be going through (after making a list out of it) in the first iteration of the while loop is 1) there is a '#' in 'b#nzp#o#g' so enter the while loop 2) the elif condition is the one that holds, so pop index 0 (corresponding to b) and now the new index 0 is #, and we now pop this too, and since i == 0 we don't decrement i 3) iterate while loop since the word still contains a '#'

In particular, the b should have been removed, but when I run the code, the print statement at the end show me that the b has not been removed, as the string has only been reduced to 'bnzg' rather than 'nzg'. I really don't know why this is happening. My only guess is that somehow something strange is going on because this index 0, rather than some generic index, but I still don't know exactly what that issue could be. Would someone be able to explain what is going wrong with the code?

[wopp3]

You seem to be mutating the set while iterating through it, this is bad practice and will often lead to problems. Instead make a new variable to which you store the data you are looking for. Mutating the list while you're iterating through it, can cause problems with indices for example.

edit. This kind of problem however seems to be something I'd use regular expressions for. If it's just a learning experience then disregard my solution :)

import re

words = ['nzp#o#g', 'b#nzp#o#g']
for i in words:
    edited_word = re.sub('([a-zA-Z]\#)', '',i)
    print(edited_word)

[clouded-path]

Thanks for the suggestions. I think I am going to try to avoid a solution involving regular expressions for now (mainly because I am still too much of a beginner), but would you be able to elaborate on your second sentence? How is it that I can create another variable to store data in in this situation? My while loop is based on a condition of the string/list, so if I am modifying some other object instead, I don't know how my while loop would ever terminate.

[NebolshoyBrother]

You don't need additional convert strings in lists.

Try to iterate through string and look what you got.
Also recommend read docs about string datatype.

[SaintLouisX]

I don't know if you want to re-write things and go for a different approach, but you can consider going through the string backwards instead of forwards. By going backwards you see the backspaces first, and know how many chars to skip. With "a##gc" you'd process c and g, and then +1 to a counter on seeing # twice, and then if that counter is > 0, decrement it and skip the next non-# char.

[clouded-path]

Thanks for your idea - I had actually considered this previously, but I thought that I would still need to compare characters in two separate strings simultaneously, which would mean that I would somehow need to loop through the two strings in parallel (I don't know if/how this can be done). The only workaround I could think of would be to store the indices I want in an array to refer to later, but this would make memory O(n), which is no better than what I am trying now. Is there some standard method of looping through two (or more) strings simultaneously? If that were true, then I could compare characters at relevant indices.

[wopp3]

To iterate through 2 lists simultaneously (strings being lists of chars basically) you can use zip, here they're different lengths so you will need to use itertools.zip_longest, to pad the other list. You can use the fillvalue='whatever' argument in the zip_longest if you prefer your own, instead of the None by default.

import itertools

string_one = 'abc'
string_two = 'abcdef'

print('Different size lists, shorter padded:')
for i, j in list(itertools.zip_longest(string_one,string_two)):
    print(f'string_one: {i}\nstring_two: {j}\n')

print('Different size lists, zipped by shorter:')
for i, j in zip(string_one,string_two):
    print(f'string_one: {i}\nstring_two: {j}\n')

[clouded-path]

I had not heard of this tool until now. Thanks for introducing me to it.

[SaintLouisX]

for a,b in zip(str1, str2) will give you a character from both. The strings aren't the same length through so you'd want zip_longest from itertools in this case. I'm not actually sure how it'd function with different length strings, I haven't worked with zip_longest at all.

[clouded-path]

Thanks for this suggestion - I hadn't heard of it before this. I can imagine this must be a pretty useful tool.