A bit verbose but easy to understand Java code using DP


  • 2
    S

    The comment explains the logic.

    public class Solution {
        public boolean isMatch(String s, String p) {
            int m = s.length(), n = p.length();
    
            boolean [][]dp = new boolean[m+1][n+1];
            dp[0][0] = true;
    
        	for (int j = 1; j <= n; j++)    {
        		if (p.charAt(j-1) == '*') {
        			dp[0][j] = j >= 2 && dp[0][j-2];
        		}    		
        	}
    
            for (int i = 1; i <= m; i++)    {
            	for (int j = 1; j <= n; j++)    {
                    if (p.charAt(j-1) == '.') {
                        dp[i][j] = dp[i-1][j-1];
                    } else if (p.charAt(j-1) == '*') {
                    	boolean val = dp[i][j-2]; // * means zero character
                    	val |= dp[i][j-1]; // * means just one match
                        
                        if (!val)	{
                        	val |= dp[i-1][j]; // * means additional matching for s[i-1]
                        	val &= p.charAt(j-2) == '.' || s.charAt(i-1) == p.charAt(j-2);
                        }
                        dp[i][j] = val;
                        
                    } else {
                        dp[i][j] = s.charAt(i-1) == p.charAt(j-1) && dp[i-1][j-1];
                    }
                }    
            }
            
            return dp[m][n];
        }
    }

Log in to reply
 

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