Shared my C++ Solution, not efficient, but more easy to understand


  • 0

    My solution can be divided into three steps

    1. find <![CDATA[CDATA_CONTENT]]>, and erase it
    2. validated <TAG_NAME> and </TAG_NAME> and check if they are at the head and tail
    3. validated <TAG_CONTENT>, just using stack to check if there have matched tag

    I do not know if I have missed some cases, If yes, please let me know, thx!

    class Solution {
    public:
        bool isValid(string code) {
            if(!validHeader(code)){
                return false;
            }
            
            int index = 0;
            while(index != string::npos){
                index = code.find("<![CDATA[");
                if(index == 0)
                    return false;
                if(index != string::npos){
                    int lindex = code.find("]]>", index);
                    if(lindex == string::npos || lindex == code.size() - 3){ //找到尾或者没有字符
                        return false;
                    }
                    code.erase(index, lindex - index + 3);
                }
            } //erase(<![CDATA]>)
            
            
            /**
             *           
             *          <TAGHeader> , TAGEnder == </....>
                        |         |               |     |
                        FIdx     RIdx          EndFIdx    
                        
                        TAGHeader doesn't like TAGEnder = '<....>' just for validTAG function
            **/           
            int TagHeaderFIdx = 0, TagHeaderRIdx = code.find('>');
            if(TagHeaderRIdx == string::npos){
                return false; //Can find '>'
            }
            string TAGHeader = code.substr(1, TagHeaderRIdx - 1); 
            int TAGEnderFIdx = code.size() - TagHeaderRIdx - 2; 
            
            if(TAGEnderFIdx < 0){
                return false; // case : "<123456>"
            }
            string TAGEnder = code.substr(code.size() - TagHeaderRIdx - 2);  //
            //TAGHeader doesn't contain '<' and '>', But TAGEnder = "</TAGHeader>"
            if(!validTag(TAGHeader) || "</" + TAGHeader + ">" != TAGEnder){
                return false;
            }
            //validated  TAG_NAME
            
            
            stack<string> st;
            index = TagHeaderRIdx + 1;
            while(index < TAGEnderFIdx){
                index = code.find("<", index);
                if(index < TAGEnderFIdx){
                    int lindex = code.find(">", index);
                    
                    if(lindex >= TAGEnderFIdx){ 
                        return false; //can't find '>'
                    }
                    
                    string Tag = code.substr(index + 1, lindex - index - 1);
                    if(Tag[0] != '/' && !validTag(Tag)){
                        return false; //invalid tag name 
                    }
                    if(Tag[0] == '/'){
                        string endTag = Tag.substr(1);
                        if(st.empty() || endTag != st.top()){ //validated lastTAG == this EndTAG
                            return false; 
                        }
                        st.pop();
                    }
                    else{
                        st.push(Tag);
                    }
                    ++index;
                }
            }//validated  TAG_CONTENT
            
            return st.empty();
        }
    private:
        //validated  header == "<........"
        bool validHeader(const string &code){
            return code.empty() || code[0]== '<';
        }
        
        bool validTag(const string &Tag){
            //validated  size
            if(Tag.size() <= 0 || Tag.size() > 9)
                return false;
            
            //validated  uppercase
            for(int i = 0; i < Tag.size(); ++i){
                if(!isupper(Tag[i]))
                    return false;
            }
            return true;
        }
    };
    

Log in to reply
 

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