Java Solution: Use startsWith and indexOf


  • 32
    F
    public class Solution {
        public boolean isValid(String code) {
            Stack<String> stack = new Stack<>();
            for(int i = 0; i < code.length();){
                if(i>0 && stack.isEmpty()) return false;
                if(code.startsWith("<![CDATA[", i)){
                    int j = i+9;
                    i = code.indexOf("]]>", j);
                    if(i < 0) return false;
                    i += 3;
                }else if(code.startsWith("</", i)){
                    int j = i + 2;
                    i = code.indexOf('>', j);
                    if(i < 0 || i == j || i - j > 9) return false;
                    for(int k = j; k < i; k++){
                        if(!Character.isUpperCase(code.charAt(k))) return false;
                    }
                    String s = code.substring(j, i++);
                    if(stack.isEmpty() || !stack.pop().equals(s)) return false;
                }else if(code.startsWith("<", i)){
                    int j = i + 1;
                    i = code.indexOf('>', j);
                    if(i < 0 || i == j || i - j > 9) return false;
                    for(int k = j; k < i; k++){
                        if(!Character.isUpperCase(code.charAt(k))) return false;
                    }
                    String s = code.substring(j, i++);
                    stack.push(s);
                }else{
                    i++;
                }
            }
            return stack.isEmpty();
        }
    }
    

  • 0
    A

    best solution I saw. An patterned way of parsing and validating. Thanks


  • 1
    T

    Nice solution, but try this test case:
    "<![CDATA[<div>]]>"


  • 1
    D

    Thank you for your clean mind. Here is C++ copy. I also clean a little bit.

    class Solution {
    public:
        bool isValid(string code) 
        {
            stack<string> stk;
    	for (int i = 0; i < code.length(); i++) {        
    	    if (i > 0 && stk.empty()) return false;
    	    if (code.substr(i, 9) == "<![CDATA[") {
    		int j = i + 9;
    		i = code.find("]]>", j);
    		if (i < 0) return false;
    		i += 2;
                } else if (code.substr(i, 2) == "</") {
    		int j = i + 2;
    		i = code.find('>', j);
    		string s = code.substr(j, i - j);
    		if (stk.empty() || s != stk.top()) return false;
    		stk.pop();
    	    } else if (code.substr(i, 1) == "<") {
    		int j = i + 1;
    		i = code.find('>', j);
    		if (i < 0 || i == j || i - j > 9) return false;
    		for (int k = j; k < i; k++) {
    	            if (!isupper(code[k])) return false;
    		}
    		string s = code.substr(j, i - j);
    		stk.push(s);
                }
    	}
    	return stk.empty();        
        }
    };
    

  • 1
    D

    This is redundant in the endtag case.

                    if(i < 0 || i == j || i - j > 9) return false;
                    for(int k = j; k < i; k++){
                        if(!Character.isUpperCase(code.charAt(k))) return false;
                    }
    

  • 0
    M

    @fatalme thanks for the awesome solution. I coded the below using your idea of using startsWith and indexOf

    public boolean isValid(String code) {
    	int i = 0;
    	Stack<String> stk = new Stack<>();
    	while (i < code.length()) {
    		if (i > 0 && stk.isEmpty()) return false;
    		int k = code.indexOf("<", i);
    		if (k == -1) return false;
    		if (code.startsWith("<![CDATA[", k)) {
    			int next = code.indexOf("]]>", k);
    			if (next == -1) return false;
    			i = next + 3;
    		} else if (code.startsWith("</", k)) {
    			int end = code.indexOf(">", k);
    			if (end == -1) return false;
    			String name = code.substring(k + 2, end);
    			if (stk.isEmpty() || !stk.pop().equals(name)) return false;
    			i = end + 1;
    		} else {
    			String trimmed = code.substring(i, k).trim();
    			if (!trimmed.isEmpty()) return false;
    			int end = code.indexOf(">", k);
    			if (end == -1) 	return false;
    			String name = code.substring(k + 1, end);
    			if (name.length() < 1 || name.length() > 9) return false;
    			for (char c : name.toCharArray()) {
    				if (c < 'A' || c > 'Z') return false;
    			}
    			stk.push(name);
    			i = end + 1;
    		}
    	}
    	return stk.isEmpty();
    }
    

  • 0

    Nice solution. Add some code to ensure the input is wrapped in a valid closed tag. Otherwise, it can't pass the test.

    public class Solution {
        public boolean isValid(String code) {
            if(code == null) return false;
            int len = code.length();
            Stack<String> stack = new Stack<>();
            
            //Ensure the code must be wrapped in a valid closed tag.
            String tag = getValidTag(code, 0, len);
            if (tag == null) return false;
            if (!code.endsWith("</"+tag+">")) return false;
            
            //find the new start and end position, after removing the outmost tag
            int i=code.indexOf("<", 1), end= len-3-tag.length(); // <tag>content ...< .>..<.>...content</tag>            
            while(i<end){
                if(code.startsWith("<![CDATA[", i)){
                    int j = code.indexOf("]]>", i+8);
                    if(j<0) return false;
                    i=j+3;
                } else if (code.startsWith("</", i)){
                    int j = code.indexOf(">", i+2);
                    if(j<0 || j==i || stack.isEmpty() || !code.substring(i+2, j).equals(stack.pop())){
                        return false;
                    }else {
                        i=j+1;
                    }                
                } else if (code.startsWith("<", i)){
                    tag = getValidTag(code, i, end);
                    if (tag == null) return false;
                    stack.push(tag);
                    i += 2+tag.length();
                } else {
                    i=code.indexOf("<", i);
                }
            }
            return stack.isEmpty();
        }
        
        private String getValidTag(String code, int open, int end){
            if(code.charAt(open)!='<') return null;
            int close = code.indexOf(">", open);
            if(close <0 || close == open+1 || close>=end || close-open > 10) return null;
            for(int i=open+1; i<close; i++){
                if(!Character.isUpperCase(code.charAt(i))) return null;
            }
            return code.substring(open+1, close);
        }
    }
    

  • 0
    B

    Noticed that if we check "<" first, it won't pass the test case...
    "

    This is the first line <![CDATA[<div>]]>
    "
    The reason is that it will never pick up and check "<![CDATA[" in this case


Log in to reply
 

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