Python: Easy Stack Optimized approach Explained
The idea here is to maintain a stack and pop from the top whenever you encounter a \'#\' symbol.\n\n\nclass Solution:\n    def backspaceCompare(self, s: str, t:
The idea here is to **maintain a stack** and **pop** from the top whenever you encounter a \'**#**\' symbol.\n\n```\nclass Solution:\n    def backspaceCompare(self, s: str, t: str) -> bool:\n        def stack_state(s):\n            stack = [] #initialize our stack\n            for c in s: #for each character in a string\n\t\t\t\t#pop one symbol from the stack if the character is \'#\'\n                if c == \'#\': \n                    if stack:\n                        stack.pop()\n                    continue\n                stack.append(c) #else if c!=\'#\' push the character to stack\n            return stack #return the final state of the stack\n\t\t\n\t\t#compare the final configurations of both the stacks for strings s and t.\n        return stack_state(s)==stack_state(t)\n```\n\n![image](https://assets.leetcode.com/users/images/d7a5608b-8785-4fba-a9ef-81c785191d9b_1651526786.8551164.png)\n\nJust consider the **stack in the form of a string** as we are just dealing with a  stack whose each element is a single character.\n\n```\nclass Solution:\n    def backspaceCompare(self, s: str, t: str) -> bool:\n        def stack_state(s):\n            stack = ""\n            for c in s:\n                if c == \'#\':\n                    if len(stack)>0:\n                        stack = stack[:-1]\n                    continue\n                stack += c\n            return stack\n        return stack_state(s)==stack_state(t)\n```\n\n![image](https://assets.leetcode.com/users/images/dcd0aab0-6fbd-488f-b86b-3511b1b44284_1651527006.2070212.png)\n\n(NOTE: The actual execution time and execution space does not matter much).\n\n**What matters more is their Asymptotic Bounds!**\nNow the asymptotic time and space complexity remains the same for both approaches.\n\n**Time Complexity = O(m + n)** owing to sequential access of strings \'s\' and \'t\', where \n* m = length of string \'s\'\n* n = length of string \'t\'.\n\n**Space Complexity =** O(m - n_hash(s) + n - n_hash(t)) = O(m + n - h) **= O(m + n)** owing to the number of elements in the stack, where \n* m = length of string \'s\'\n* n = length of string \'t\'\n* n_hash(x) = a function that counts the number of \'#\' symbols in a string.\n* h = n_hash(s) + n_hash(t) where s and t are our input strings.
['String', 'Stack', 'Python']