Python/JS/Java/C++ O( n ) sol by stack. [w/ Comment]
Time Complexity:\nO( n ) for loop iteration\n\nSpace Complexity:\nO( n ) for stack and output string generation\n\n\n\n---\n\n\nclass Solution:\n    def backspa
Time Complexity:\nO( n ) for loop iteration\n\nSpace Complexity:\nO( n ) for stack and output string generation\n\n\n\n---\n\n```\nclass Solution:\n    def backspaceCompare(self, S: str, T: str) -> bool:\n        \n        stack_s, stack_t = [], []\n        \n        # --------------------------------------\n        def final_string( stk, string ):\n            \n            for char in string:\n                \n                if char != \'#\':\n\t\t\t\t\t# push new character into stack\n                    stk.append( char )\n                    \n                elif stk:\n                    # pop last charachter from stack, as a result of backspace operation\n                    stk.pop() \n                    \n            \n            return \'\'.join(stk)\n        \n        # --------------------------------------\n        \n        return final_string( stack_s, S ) == final_string( stack_t, T )\n        \n        \n```\n\n---\n\n**Javascript**:\n\n```\nvar backspaceCompare = function(s, t) {\n    \n    \n    var finalString = function( keyIn ){\n        \n        let stack = [];\n        \n        for( let char of keyIn ){\n            \n            if( char != \'#\'){\n                stack.push( char );\n                \n            }else if( stack.length != 0 ){\n                stack.pop();\n            }\n            \n        }\n        \n        return stack.join("");\n    };\n    \n    return finalString(s) == finalString(t);\n    \n};\n```\n\n---\n\n**Java:**\n\n```\nclass Solution {\n    public boolean backspaceCompare(String s, String t) {\n        \n        return finalString(s).equals( finalString(t) );\n    }\n    \n    private String finalString( String keyIn ){\n        \n        Stack< Character > stk = new Stack< Character >();\n        \n        for( Character ch : keyIn.toCharArray() ){\n            \n            if( ch != \'#\' ){\n                stk.push( ch );\n                \n            }else if( !stk.isEmpty() ){\n                stk.pop();\n            }\n        }\n        \n        return stk.toString();\n        \n    }\n}\n```\n\n---\n\n**C++**:\n\n```\nclass Solution {\npublic:\n    bool backspaceCompare(string s, string t) {\n        \n        return finalString(s) == finalString(t);\n    }\n    \nprivate:\n    string finalString(string keyIn ){\n\n        vector<char> stk;\n\n        for( char& ch : keyIn ){\n\n            if( ch != \'#\'){\n                stk.push_back( ch );\n\n            }else if( stk.size() != 0 ){\n                stk.pop_back();\n            }\n        }\n        \n        return string( begin(stk), end(stk) );\n    };\n        \n};\n```\n\n---\n\nReference:\n\n[1] [Python official docs about list and stack-related operation.](https://docs.python.org/3/tutorial/datastructures.html#more-on-lists)\n\n[2] [Wiki: Stack ( abstract data type)](https://en.wikipedia.org/wiki/Stack_(abstract_data_type))\n\n[3] [Youtube: Stack introduction with Python](https://youtu.be/L3ud3rXpIxA)\n\n[4] [Python official docs about str.join( ... )](https://docs.python.org/3/library/stdtypes.html#str.join)\n
['String', 'Stack', 'C', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']