My AC DP solution for this problem, asking for improvements.


  • 20
    S
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        
        if (s == null || p == null) {
            return false;
        }
        
        boolean[][] OPT = new boolean[m+1][n+1];
        OPT[0][0] = true;
        
        for (int i = 1; i <= m; i++) {
            OPT[i][0] = false;
        }
        for (int j = 1; j <= n; j++) {
            OPT[0][j] = (p.charAt(j-1) == '*') && (j-2 >= 0) && OPT[0][j-2];
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                OPT[i][j] = ((OPT[i-1][j-1]) && equals(s, p, i-1, j-1))
                        ||  ((OPT[i-1][j] || OPT[i][j-1]) 
                            && (p.charAt(j-1) == '*') 
                            && equals(s, p, i-1, j-2))
                        ||  ((p.charAt(j-1) == '*') && (j-2 >= 0) && OPT[i][j-2]);
            }
        }
        
        return OPT[m][n];
    }
    
    private boolean equals(String s, String p, int si, int pi) {
        return (s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '.');
    }
    

    Basically, the OPT[i][j] means preceding substring of length i of s and length j of p. For any two substrings, the value of OPT[i][j] can be from one of following four cases:

    • case 1: OPT[i-1][j-1] is true, and ith character of s is equal to j th character of p. Or j th character of p is '.'
    • case 2: OPT[i-1][j] is true, then my pattern now is '*' and preceding character is equal to incoming character of s
    • case 3: OPT[i][j-1] is true, then my pattern now is '*' which can match an empty string
    • case 4: OPT[i][j-2] is true, and the pattern like (a*) matches an empty string

    base case is the OPT[0][0], OPT[i][0], OPT[0][j].


  • 7
    R

    I found I was using the exact algorithm as you did. So I post one for your references.It has no additional brace.

    It is very difficult to write a pretty code in string operations by Java due to .charAt().

    By the way
    Your value assignment in the nested loop is indeed a pain to read(At least for me ). I do suggest you to give more lines on that part.

    public class RegularExpressionMatching {
        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
    L
    This post is deleted!

  • 0
    L

    "" match "a*" is true, "" match "a**" is false, but "" match "a***" is true again.
    This is interesting. Hard to define consecutive "*"s.


  • 0
    Z

    I think you don't need two checks j>1. If p.charAt(0) == * then the pattern p is illegal. The star * should be preceded by any symbol except *.


  • 0
    M

    Yes, I think "false" assignment is not necessary either as that's the default in Java.


  • 0
    B

    If I change this line
    matrix[i][j]=matrix[i-1][j]||matrix[i][j-2]||matrix[i][j-1];

    to
    matrix[i][j]=matrix[i-1][j]||matrix[i][j-2]||matrix[i-1][j-1];

    still AC,
    but why?


  • 1
    M

    @BZ: Great observation. Because matrix[i][j-1] check is unnecessary.

    matrix[i][j - 1] checks for 1 appearance of the previous element; however, matrix[i - 1][j] checks for string s substring ending in previous element [i - 1] matches string p substring ending in [j], which includes 0 appearance of the previous element, and since we're inside the if statement, this confirms 1 appearance of the previous element.

    i.e. matrix[i - 1][j]: aab vs aab*: depends on aa vs aab*
    no need to check depends on aab vs aab


  • 0
    R

    I think you'd better check "s" and "p" are null or not before defining "m" and "n".


Log in to reply
 

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