Sharing my simple solution in java 14ms


  • 0
    Z

    Most people solve the problem using dp,thereby i consider that sharing my solution should be necessary.

    public boolean isMatch(String s, String p) {
    		List<ExpPattern> patterns = makePattern(p);
    //		 for(ExpPattern pattern:patterns){
    //		 System.out.println(pattern);
    //		 }
    		return isMatched(s, patterns);
    	}
    
    	public boolean isMatched(String s, List<ExpPattern> patterns) {
    		// System.out.println(s+""+patterns);
    		int sIndex = 0;
    		for (int j = 0; j < patterns.size(); j++) {
    			ExpPattern pattern = patterns.get(j);
    			if (pattern.atLeast) {
    				for (int i = 0; i < pattern.matchNum; i++) {
    					if (sIndex >= s.length() || pattern.c != '.'
    							&& pattern.c != s.charAt(sIndex)) {
    						return false;
    					}
    					sIndex++;
    				}
    				int tmpInd = sIndex;
    				int sameNum = 0;
    				for (; tmpInd < s.length(); tmpInd++) {
    					if (pattern.c!='.' && s.charAt(tmpInd) != pattern.c) {
    						break;
    					}
    					sameNum++;
    				}
    //				System.out.println("sameNum" + sameNum);
    				if (j == patterns.size() - 1) {
    					// last
    					sIndex += sameNum;
    				} else {
    					for (int i = 0; i <= sameNum; i++) {
    						if (isMatched(s.substring(sIndex + i, s.length()),
    								patterns.subList(j + 1, patterns.size()))) {
    							return true;
    						}
    					}
    					return false;
    				}
    
    			} else {
    				for (int i = 0; i < pattern.matchNum; i++) {
    					if (sIndex >= s.length() || pattern.c != '.'
    							&& pattern.c != s.charAt(sIndex)) {
    						return false;
    					}
    					sIndex++;
    				}
    			}
    		}
    		return sIndex >= s.length();
    
    	}
    
    	public List<ExpPattern> makePattern(String p) {
    		List<ExpPattern> patterns = new ArrayList<ExpPattern>();
    		for (int i = 0; i < p.length(); i++) {
    			ExpPattern pattern = patt(i, p);
    			i = pattern.i;
    			patterns.add(pattern);
    		}
    		return patterns;
    	}
    
    	public ExpPattern patt(int i, String p) {
    
    		int tmp = i + 1;
    		char c = p.charAt(i);
    		boolean atLeast = false;
    //		int num = 0;
    //
    //		if (i == p.length() - 1) {
    //			num = 1;
    //		}
    		int num = 1;
    		
    		if (tmp<p.length() && p.charAt(tmp) == '*') {
    			atLeast = true;
    			num = 0;
    			tmp++;
    		}
    		for (; tmp < p.length(); tmp++) {
    		
    			if(p.charAt(tmp) == '*') {
    				atLeast = true;
    				continue;
    			}
    			if (p.charAt(tmp) != c) {
    				break;
    			}
    
    			if (tmp == p.length() - 1 || p.charAt(tmp + 1) != '*') {
    				num++;
    			}
    		}
    
    		ExpPattern pattern = new ExpPattern();
    		pattern.atLeast = atLeast;
    		pattern.c = c;
    		pattern.matchNum = num;
    		i = tmp - 1;
    		pattern.i = i;
    		return pattern;
    
    	}
    
    

Log in to reply
 

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