Share my C++ solution using replace but not stack, 4ms


  • 0
    S
    basic situation, leaf node: 1,#,#
    advance situation 1, left child is leaf: 2,1,#,#,#
    advance situation 2, right child is leaf: 2,#,1,#,#
    

    repalce node to #, so we got:

    advance situation 1: 2,#,#
    advance situation 2: 2,#,#
    

    we call the leaf node is a pattern. the ideas is iteratively repalce leaf node to # until no pattern to find。

    So, we going to find a pattern, repalce it, and then do it again and again...

    class Solution {
    public:
        bool isValidSerialization(string preorder) {
            string& s = preorder;
            while (s.size() >= 5) {
                bool find_pattern = false;
                for (int i = s.size()-1; i>= 4; i--) {
                    if (s[i] == '#' && s[i-2] == '#' && s[i-4] != '#') {
                        find_pattern = true;
                        int j = i-4-1;
                        /* find the start place of pattern */
                        while (j > 0 && s[j] != ',') j--; 
                        s.replace(j+1, i-j, "#"); /* replace s[j+1, i]  to "#" */
                        break;  /* start a trun search from the end */
                    }
                }
                if (!find_pattern) break;
            }
            
            /* boundary: empty tree */
            return (s.size() == 1 && s[0] == '#');
        }
    };
    
    
    void test(string s, bool result) {
        Solution so;
        bool ret = so.isValidSerialization(s);
        if (ret != result) {
            cout << "test case fail: " << endl;
            cout << s << endl;
            cout << "true result: " << result<< endl;
            cout << "false ret: " << ret << endl;
        }
    }
    
    int main()
    {
        test("#", true); // empty tree
    
        // true cases
        test("1,#,#", true);
        test("1,2,#,#,#", true);
        test("9,3,4,#,#,1,#,#,2,#,6,#,#", true);
    
        // false cases
        test("1,#", false);
        test("1,#,#,#,#", false);
        test("9,#,#,1", false);
        test("9,3,4,#,#,1,#,#,#,2,#,6,#,#", false);
        return 0;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.