3 C/C++ char array vs string as stack||beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nSolving it in O(n) is easy where n=len(s)+len(t). But solving it in O(n) time with O(1)
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSolving it in O(n) is easy where n=len(s)+len(t). But solving it in O(n) time with O(1) space needs tricks!\n\nHere present 2 solutions using C++ string as stack. The C solution uses 2 pointers & is in fact a modification of the 2nd C++ solution.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe operations pop_back, push_back for C++ string are the same as the operations pop, push for stack.\n\nThe second solution can be furthermore modified into 2-pointer solutions. The C code solution is the implementation of such conversion.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)\\to O(1)$$\n# Code\n```\nclass Solution {\npublic:\n    bool backspaceCompare(string s, string t) {\n        vector<char> sc, tc;\n        for(char c: s){\n            if (c>=\'a\' && c<=\'z\') sc.push_back(c);\n            else if (c=\'#\'&& !sc.empty()) sc.pop_back();\n        }\n        for(char c: t){\n            if (c>=\'a\' && c<=\'z\') tc.push_back(c);\n            else if (c=\'#\'&& !tc.empty()) tc.pop_back();\n        }\n        return sc==tc;\n    }\n};\n```\n# Code using strings as stacks time 0 ms beats 100%\n```\nclass Solution {\npublic:\n    bool backspaceCompare(string s, string t) {\n        int nS=0, nT=0;\n        while (!s.empty() || !t.empty()){\n            while(!s.empty()){\n                if (s.back()==\'#\') nS++, s.pop_back();\n                else if (nS>0) nS--, s.pop_back();\n                else break;\n            }\n            while(!t.empty()){\n                if (t.back()==\'#\') nT++, t.pop_back();\n                else if (nT>0) nT--, t.pop_back();\n                else break;\n            }\n            if (!s.empty()&& !t.empty() &&s.back()!=t.back()) return 0;\n            if ((s.empty()&&!t.empty())||(!s.empty()&&t.empty()))\n                return 0;\n            if (!s.empty())s.pop_back();\n            if (!t.empty())t.pop_back();\n        }\n        return 1;\n    }\n};\n\n```\n# C code using 2 pointers runs in 0 ms and beats 100%\n```\nbool backspaceCompare(char * s, char * t){\n    int nS=0, nT=0;\n    register int i, j;\n    for(i=strlen(s)-1, j=strlen(t)-1; i>=0||j>=0; i--, j--){\n        while(i>=0){\n            if (s[i]==\'#\') nS++, i--;\n            else if (nS>0) nS--, i--;\n            else break;\n        }\n        while(j>=0){\n            if (t[j]==\'#\') nT++, j--;\n            else if (nT>0) nT--, j--;\n            else break;\n        }\n        if (i>=0 && j>=0 && s[i]!=t[j]) return 0;\n        if ((i>=0)^(j>=0)) return 0;\n    }\n    return 1;\n}\n```
['Two Pointers', 'String', 'Stack', 'C', 'C++']