Python O(N) Time O(1) Space Solution | Explained
This is a Python Version of the Java Solution utilizing O(1) space because it seemed really intuitive to me.(https://leetcode.com/problems/backspace-string-comp
This is a Python Version of the Java Solution utilizing O(1) space because it seemed really intuitive to me.(https://leetcode.com/problems/backspace-string-compare/solution/)\n\nIn this solution, a **valid character** refers to anything that is not a "#". I have worked out an example, if you already know the logic you can skip ahead to the code.\n\nThe idea is, we traverse both the strings from the end. We declare i and j to be equal to the length of the strings - 1.\n\nSay we are given, "ab#c" and "ad#c"\nNow, we traverse from the end. \n* i = 3 and j = 3:\n\t* We see that S[i] and T[j] are **valid characters**. Hence, we just compare them and then reduce the value of i and j respectively. Now we have to compare "ab#" and ad#"\n* i = 2 and j = 2:\n\t* We see that S[i] is not a **valid character**. Therefore, we must skip the next **valid character** that we might encounter. In this case, we skip "b". Now comparision must be done with the next **valid character** that was not skipped, which is "a". Similarly in the case of T[j], the next **valid character** is "a". We compare both, and they match.\n\nIf that sounds confusing, I would recommend looking at the code, and working out the example that I gave using the code.\n\n\n\n```\nclass Solution:\n\tdef backspaceCompare(self, S, T):\n\t\ti = len(S) - 1\t\t\t# Traverse from the end of the strings\n\t\tj = len(T) - 1\n\n\t\tskipS = 0              # The number of backspaces required till we arrive at a valid character\n\t\tskipT = 0\n\n\t\twhile i >= 0 or j >= 0:\n\t\t\twhile i >= 0:\t\t\t\t\t# Ensure that we are comparing a valid character in S\n\t\t\t\tif S[i] == "#" :\n\t\t\t\t\tskipS += 1\t\t\t\t# If not a valid character, keep times we must backspace.\n\t\t\t\t\ti = i - 1\n\n\t\t\t\telif skipS > 0:\n\t\t\t\t\tskipS -= 1\t\t\t\t# Backspace the number of times calculated in the previous step\n\t\t\t\t\ti = i - 1\n\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\n\t\t\twhile j >= 0:\t\t\t\t\t# Ensure that we are comparing a valid character in T\n\t\t\t\t\tif T[j] == "#":\n\t\t\t\t\t\tskipT += 1\t\t\t# If not a valid character, keep times we must backspace.\n\t\t\t\t\t\tj = j - 1\n\n\t\t\t\t\telif skipT > 0:\n\t\t\t\t\t\tskipT -= 1\t\t\t# Backspace the number of times calculated in the previous step\n\t\t\t\t\t\tj = j - 1\n\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\n\t\t\tprint("Comparing", S[i], T[j])\t\t# Print out the characters for better understanding.\n\n\t\t\tif i>= 0 and j >= 0 and S[i] != T[j]:    # Compare both valid characters. If not the same, return False.\n\t\t\t\treturn False\n\n\t\t\tif (i>=0) != (j>=0):\t\t# Also ensure that both the character indices are valid. If it is not valid,\n\t\t\t\treturn False\t\t\t#  it means that we are comparing a "#" with a valid character.\n\n\t\t\ti = i - 1\n\t\t\tj = j - 1\n\n\t\treturn True\t\t\t\t\t# This means both the strings are equivalent.\n```\n
['Python', 'Python3']