Share my AC solution


  • 1
    Y

    public boolean isMatch(String s, String p) {

        int m = s.length(), n = p.length();
        boolean[][] matrix = new boolean[m+1][n+1];
        
        //s="" p="" is true
        matrix[0][0] = true;
        
        //Handle cases like s="" p="****"
        for(int i=1;i<=n;i++)
        {
            if(p.charAt(i-1) == '*')
                matrix[0][i] = true;
            else
                break;
        }
            
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                char c = p.charAt(j-1);
                if(c != '*')
                    matrix[i][j] = matrix[i-1][j-1] && (s.charAt(i-1) == c || c == '?');
                else
                {
                    //matrix[i][j-1] => * is empty
                    //matrix[i-1][j] => match sequence of characters
                    matrix[i][j] = matrix[i][j-1] || matrix[i-1][j];
                }
            }
        }
        return matrix[m][n];
    

    }


Log in to reply
 

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