The dumb AC code.


  • 1
    N

    I have spent a long time to figure this problem out. Here is my AC code in java, it's a little bit complex so I added a lot of comments to make it more understandable ( and in case I forget the logic someday ) :

    public class Solution {
        public boolean isMatch(String s, String p) {
    		return isMatch(s, 0, s.length() - 1, p, 0, p.length() - 1);
    	}
    
    	public boolean isMatch(String s, int sS, int sE, String p, int pS, int pE) {
    	    // empty string , no pattern: can match
    		if (sS > sE && pS > pE)
    			return true;
    
            // non-empty string,  no pattern: cannot match
    		if (sS <= sE && pS > pE)
    			return false;
    
            // empty string, non-empty pattern: test if the pattern can match an empty string
    		if (sS > sE && pS <= pE)
    			return canMatchEmpty(p, pS, pE);
    
    		// algorithm begins:
    		
    		// 1. if the first 2 chars of pattern are "a*" or ".*":
    		if (pS + 1 <= pE && p.charAt(pS + 1) == '*') {
    		    
                // because "a*" or ".*" can match an empty string, 
                // if the rest part of the pattern can match the whole string,
                // we know the whole pattern can match it too.
    			if (isMatch(s, sS, sE, p, pS + 2, pE))
    				return true;
    
                // "a*" or ".*" can match a bunch of chars too, so for every position
                // in string, we test:
                // 1. whether the left part can match this 'sterisk' pattern (which has only two chars)
                // 2. whether the right part (may be an empty string) can match the rest part of the pattern
    			for (int i = sS; i <= sE; i++) {
    				if (matchSterisk(s, sS, i, p.charAt(pS))
    						&& isMatch(s, i + 1, sE, p, pS + 2, pE))
    					return true;
    			}
    
                // match failed
    			return false;
    		}
    
            // 2. the first char of pattern is '.':
    		if (p.charAt(pS) == '.') {
    		    // a '.' can match any single number, so we can safely skip it
    			return isMatch(s, sS + 1, sE, p, pS + 1, pE);
    		}
    
            // 3. the first char of pattern is a letter:
    		return s.charAt(sS) == p.charAt(pS)
    				&& isMatch(s, sS + 1, sE, p, pS + 1, pE);
    	}
    
    	// if a pattern can match empty string, it should be like 'a*a*.*b*'
    	private boolean canMatchEmpty(String p, int pS, int pE) {
    		if (!(pE - pS >= 1 && (pE - pS + 1) % 2 == 0))
    			return false;
    		for (int i = 0; i <= pE - pS; i++) {
    			if (i % 2 == 0 && p.charAt(pS + i) == '*')
    				return false;
    			if (i % 2 == 1 && p.charAt(pS + i) != '*')
    				return false;
    		}
    		return true;
    	}
    
        // test whether a string can match a sterisk pattern, which is like c + '*'
    	private boolean matchSterisk(String s, int sS, int sE, char c) {
    		if (c == '.')
    			return true;
    		for (int i = sS; i <= sE; i++) {
    			if (s.charAt(i) != c)
    				return false;
    		}
    		return true;
    	}
    }

  • 0
    R

    Take a look at my solution.

        public boolean isMatch(String s, String p) {
    	if (s==null&&p==null) return true;
    		
    	if (s.length()==0&&p.length()==0) return true;
    	
    	boolean[][] matrix = new boolean[s.length()+1][p.length()+1];
    	
    	matrix[0][0]=true;
    	
    	for (int i=1;i<=s.length();i++)
    		matrix[i][0]=false;
    	
    	for (int j=1;j<=p.length();j++)
    		if (p.charAt(j-1)=='*'&&j>1)
    			matrix[0][j]=matrix[0][j-2];
    		else matrix[0][j]=false;
    	
    	for (int i=1;i<=s.length();i++)
    		for (int j=1;j<=p.length();j++)
    			
    			if (p.charAt(j-1)==s.charAt(i-1)||p.charAt(j-1)=='.')
    				matrix[i][j]=matrix[i-1][j-1];
    			
    			else if (p.charAt(j-1)=='*'&&j>1)   				
    				if (p.charAt(j-2)==s.charAt(i-1)||p.charAt(j-2)=='.')
    					matrix[i][j]=matrix[i-1][j]||matrix[i][j-2]||matrix[i][j-1];
    					//matrix[i-1][j]:abb vs ab*: depends on ab vs ab*
    					//matrix[i][j-2] a  vs ab*  depends on a vs a
    					//matrix[i][j-1] ab vs ab*: depends on ab vs ab 
    				else 
    					matrix[i][j]=matrix[i][j-2]; 
    	
    			else matrix[i][j]=false;
    	
    	return matrix[s.length()][p.length()];
    }

  • 0
    S

    Hi, @reeclapple, can you add some explanation of your solution? I am confused.


  • 0
    J

    Thank you!!! It took me a while to get the logic.


Log in to reply
 

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