Golang O(n) time, O(1) space simple code with explanation, beats 100%
Intuition\nYou might have figured out by now that comparing character by character starting from the front is not going to work. But we can make it work if we c
# Intuition\nYou might have figured out by now that comparing character by character starting from the front is not going to work. But we can make it work if we compare from the end.\n\n# Approach\nAssume that there were no backspaces and we only wanted to compare two strings from last to first characters, the below code will work - \n\n```\nfunc normalCompare(s string, t string) bool {\n    si := len(s) - 1\n    ti := len(t) - 1\n\n    // iterate from last to first character for both strings\n    for si >= 0 && ti >= 0 {\n        // if current chars are not same, strings are not same\n        if si >= 0 && ti >= 0 && s[si] != t[ti] {\n            return false\n        }\n\n        si -= 1\n        ti -= 1\n    }\n\n    // if both strings are of uneuqal length, this will be false\n    return si == ti\n}\n```\n\nAs there can be backspaces for the strings in this question, the above code won\'t work as it is. But we can modify it to clear the backspaces first right before comparing the current indexes. We write another function `clearBackspaces` which given the str and an index, decrements index per the backspace characters. And then do the same comparison as above. Check the below code for the implementation.\n\n# Complexity\n- Time complexity: O(n) - we iterate over the whole string once\n\n- Space complexity: O(1)\n\n# Code\n```\nfunc backspaceCompare(s string, t string) bool {\n    si := len(s)-1\n    ti := len(t)-1\n\n    // iterate from last to first character for both strings\n    for si >= 0 && ti >= 0 {\n\n        si = clearBackspaces(s, si)\n        ti = clearBackspaces(t, ti)\n        \n        // if current characters are not same after taking care\n        // of the end backspaces, strings are not same\n        if si >= 0 && ti >= 0 && s[si] != t[ti] {\n            return false\n        }\n\n        si -= 1\n        ti -= 1\n    }\n\n    // clear any final backspaces remaining\n    si = clearBackspaces(s, si)\n    ti = clearBackspaces(t, ti)\n\n    return si == ti\n}\n\n// given a string s and a position i, decrement i to the point where\n// s[i] won\'t be deleted/backspaced\nfunc clearBackspaces(s string, i int) int {\n    backspacesCnt := 0\n    // keep track of backspaces and apply them by decrementing i\n    for i >= 0 && (backspacesCnt > 0 || s[i] == \'#\') {\n        if s[i] == \'#\' {\n            // we\'ll take care of this in future loop iterations\n            backspacesCnt++\n        } else {\n            // we\'re taking care of an earlier backspace in this iteration\n            backspacesCnt--\n        }\n        i--\n    }\n\n    // we\'ve reached a point where s[i] is neither a backspace nor affected by a backspace\n    return i\n}\n```
['Go']