Java solution. Sequentially build current structure, use stack for tag matching


  • 1
    H

    Use a stack to match start_tag and end_tag pairs. Everything else will be "any characters"
    which can be ignored, or cdata which can be detected once and throw away. Be careful of
    "<A></A><B></B>" case. The entire code has to be exact ONE valid closed tag.

    public class Solution {
    	public boolean isValid(String code) {
    		if (!code.startsWith("<")) return false;
    		if (code.length() < 2 || !(code.charAt(1) >= 'A' && code.charAt(1) <= 'Z')) return false;
    		
    		Stack<String> stack = new Stack<>();
    		String cur = "";
    		for (int i = 0; i < code.length(); i++) {
    			cur += code.charAt(i);
    			if (cur.startsWith("<![CDATA[")) {
    				if (cur.endsWith("]]>")) {
    					cur = "";
    				}
    			} else if (cur.startsWith("</")) {
    				if (cur.endsWith(">")) {
    					String tag = cur.substring(2, cur.length()-1);
    					if (stack.isEmpty() || !stack.peek().equals("<"+tag+">")) return false;
    					stack.pop();
    					cur = "";
    					if (i < code.length()-1 && stack.isEmpty()) return false;
    				}
    			} else if (cur.startsWith("<")) {
    				if (cur.endsWith(">")) {
    					if (!valid_tag(cur)) return false;
    					stack.push(cur);
    					cur = "";
    				}
    			} else {
    				cur = "";
    			}
    		}
    		return stack.isEmpty() && cur.length() == 0;
            }
    	boolean valid_tag(String tag) {
    		if (!tag.startsWith("<") || !tag.endsWith(">")) return false;
    		if (tag.length() < 3 || tag.length() > 11) return false;
    		for (int i = 1; i < tag.length()-1; i++) {
    			char c = tag.charAt(i);
    			if (!Character.isUpperCase(c)) return false;
    		}
    		return true;
    	}
    }
    
    

Log in to reply
 

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