123ms java solution with Pattern API


  • 0
    V
    public boolean isMatch(String s, String p) {
    	if (p == null || p.length() == 0) {
    		return s == null || s.length() == 0;
    	}
    	return Pattern.compile(p).matches(s);
    }
    
    private static class Pattern {
    	private static PatternElement DOT_ELEMENT = new PatternElement() {};
    	
    	List<PatternElement> elements = new ArrayList<>();
    	
    	public static Pattern compile(String p) {
    		Pattern result = new Pattern();
    		PatternElement prevElement = null;
    		for (int i = 0; i < p.length(); i++) {
    			char c = p.charAt(i);
    			PatternElement curElement;
    			if (c == '*') {
    				curElement = new AnyCountElement(prevElement);
    				result.elements.add(curElement);
    				prevElement = null;
    				continue;
    			} else if (c == '.') {
    				curElement = DOT_ELEMENT;
    			} else {
    				curElement = new TextElement(c);
    			}
    			if (prevElement != null) {
    				result.elements.add(prevElement);
    			}
    			prevElement = curElement;
    		}
    		if (prevElement != null) {
    			result.elements.add(prevElement);
    		}
    		return result;
    	}
    	
    	public boolean matches(String s) {
    		return matches(s, 0, 0);
    	}
    	
    	/*
    	q w e r t y
    	0 1 2 3 4 5
    	length = 6
    	*/
    	private boolean matches(String s, int cInd, int elementInd) {
    		if (elementInd >= elements.size()) {
    			return cInd >= s.length();
    		}
    		if (cInd >= s.length()) {
    			return elements.stream().skip(elementInd).allMatch(e -> e.size() < 0);
    		}
    		PatternElement curElement = elements.get(elementInd);
    		if (elementInd == elements.size() - 1) {
    			return curElement.size() < 0 
    					? curElement.matches(s, cInd, s.length())
    					: (cInd == s.length() - 1 && curElement.matches(s.charAt(cInd)));
    		}
    		
    		if (curElement.size() < 0) {
    			for (int i = cInd; i <= s.length(); i++) {
    				if (curElement.matches(s, cInd, i) 
    						&& matches(s, i, elementInd + 1)) {
    					return true;
    				}
    			}
    		} else {
    			return curElement.matches(s.charAt(cInd)) && matches(s, cInd + 1, elementInd + 1);
    		}
    		return false;
    	}
    }
    
    private interface PatternElement {
    	default boolean matches(String s, int from, int to) {
    		return to - from + 1 == 1;
    	}
    	
    	default boolean matches(char c) {
    		return true;
    	}
    	
    	default int size() { return 1; }
    }
    
    private static class TextElement implements PatternElement {
    	char ch;
    
    	public TextElement(char ch) {
    		this.ch = ch;
    	}
    
    	@Override
    	public boolean matches(String s, int from, int to) {
    		return to - from + 1 == 1 && s.charAt(from) == ch;
    	}
    
    	@Override
    	public boolean matches(char c) {
    		return ch == c;
    	}
    }
    
    private static class AnyCountElement implements PatternElement {
    	PatternElement element;
    
    	public AnyCountElement(PatternElement element) {
    		this.element = element;
    	}
    
    	@Override
    	public boolean matches(String s, int from, int to) {
    		if (to - from + 1 == 0) {
    			return true;
    		}
    		
    		for (int i = from; i < to; i++) {
    			if (!this.matches(s.charAt(i))) {
    				return false;
    			}
    		}	
    		return true;
    	}
    
    	@Override
    	public boolean matches(char c) {
    		return element.matches(c);
    	}
    
    	@Override
    	public int size() {
    		return -1;
    	}
    }

Log in to reply
 

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