[C++] O(n) time and O(1) space easy to do
solution:\nTwo steps to solve this problem:\n    Step 1. backspace to get new string.\n    Step 2. compare two new strings.\n\nAccording to this solution, we ca
##### **solution:**\nTwo steps to solve this problem:\n    `Step 1. backspace to get new string.`\n    `Step 2. compare two new strings.`\n\nAccording to this solution, we can write the code easily.\nIn my first attampt, I did an O(n) space code as *`Code 1`*.\nThen, thanks for [Bhu](lhttps://leetcode.com/bhuvanbgmailcom/)\'s comments. I get the O(1) space answer as *`Code 2`*.\n\n***`Code 1`*: O(n) space & O(n) time:**\n```\nclass Solution {\nprivate:\n    string backspace(string s){\n        int i, j;\n        for(i=j=0; i<s.length(); ++i){\n            if(s[i]==\'#\'){\n                if(j>0) j--;\n            }\n            else{\n                s[j++] = s[i];\n            }\n        }\n        return s.substr(0, j);\n    }\npublic:\n    bool backspaceCompare(string S, string T) {\n        S = backspace(S);\n        T = backspace(T);\n        return S==T;\n    }\n};\n```\n\n***`Code 2`*: O(1) space & O(n) time:**\n```\nclass Solution {\nprivate:\n    int backspace(string &s){\n        int i, j;\n        for(i=j=0; i<s.length(); ++i){\n            if(s[i]==\'#\'){\n                if(j>0) j--;\n            }\n            else{\n                s[j++] = s[i];\n            }\n        }\n        return j;\n    }\npublic:\n    bool backspaceCompare(string S, string T) {\n        int sLen = backspace(S);\n        int tLen = backspace(T);\n        if (sLen != tLen) return false;\n        for (int i = 0; i < sLen; i++) {\n            if (S[i] != T[i]) return false;\n        }\n        return true;\n    }\n};\n```
[]