A better split function for you !!! @rainbow


  • 0
    2

    Dear all, I think you should quickly implement the no bug string split function , here is a fast and elegent impmentation refered to the stackoverflow.

    Here is my AC implementation . My idea is the same to the top voted solution to cut the leaves node and set the root as the leave.

    class Solution {
    public:
        bool isValidSerialization(string preorder) {
            vector<string> elems;
            char delim = ',';
            split(preorder, delim, elems);
            vector<bool> stack(elems.size(), false);
            int end = 0;
            for (auto elem : elems) {
                /** the root is null **/
                if (end == 1 && stack[end - 1] == false)  return false;
                /** add the current the elem into the stack **/
                stack[end++] = !(elem == "#");
                /** key parts : find 2 leaves node, just update to del the leaves and set the root as leave **/
                while (end >= 3 && stack[end - 3] && !stack[end - 2] && !stack[end - 1]) {
                    stack[end - 3] = false;
                    end -= 2;
                }
            }
            return end == 1 && !stack[0];
        }
        /** this implementation does not skip the null string between the split char **/
        void split(const string &s, char delim, vector<string> &elems) {
            stringstream ss(s);
            string item;
            while(getline(ss, item, delim)) {
                elems.push_back(item);
            }
        }
    };

Log in to reply
 

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