my ugly C++ solution


  • 0
    M
    class Solution {
    public:
        bool isValid(string code) {
            if (code.size() < 7) // 7 is the minimum size of the input string <A></A>
                return false;
                
            stack<string> mstack;
            
            int i = 0;
            if (code[i] != '<' || (code[i] == '<' && (code[i+1] < 'A' || code[i+1] > 'Z'))) {
                return false;
            }
                
            while (i < code.size()) {
                while (i < code.size() && code[i] != '<') {
                    i++;}
                if (i > code.size()-4) { // not enough left for a tag or cdata
                    return false;
                }
                i++;
                // check whether it's cdata: <![CDATA[CDATA_CONTENT]]>
                if (code[i] == '!') {
                    i++;
                    if (code.substr(i, 7) != "[CDATA[") {
                        return false;
                    }
                    i += 7;
                    bool flag = true;
                    while (i < code.size()-2) {
                        if (code[i] == ']' && code[i+1] == ']' && code[i+2] == '>') {
                            flag = false;
                            i += 2;
                            break;
                        }
                        i++;
                    }
                    if (flag) {
                        return false;
                    }
                }
                // not cdata, then it should be a tag_name, tag_name_end?
                else if (code[i] == '/') {
                    i++;
                    int start = i;
                    while (i < code.size() && code[i] != '>') {
                        if (code[i] < 'A' || code[i] > 'Z') {
                            return false;
                        }
                        i++;
                    }
                    if (i == code.size()) {
                        return false;
                    }
                    if (i - start > 9 || i - start < 1) {
                        return false;
                    }
                    if (!mstack.empty() && mstack.top() == code.substr(start, i-start)) {
                        mstack.pop();
                        if (mstack.empty() && i != code.size()-1)
                            return false;
                    }
                    else {
                        return false;
                    }
                }
                // it's a tag_name_start, put it in stack
                else {
                    int start = i;
                    while (i < code.size() && code[i] != '>') {
                        if (code[i] < 'A' || code[i] > 'Z') {
                            return false;
                        }
                        i++;
                    }
                    if (i - start > 9 || i - start < 1) {
                        return false;
                    }
                    mstack.push(code.substr(start, i-start));
                }
                i++;
            }
            
            return mstack.empty();
        }
    };
    

Log in to reply
 

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