Failing for large input


#1
public int isMatch(final String A, final String B) {
        int [][]dp = new int[A.length()+1][B.length()+1];
        for(int i=0;i<B.length();i++){
            dp[0][i] = 1;
        }
        for(int i=1;i<=A.length();i++){
            for(int j=1;j<=B.length();j++){
                if(dp[i][j-1] == 1){
                    dp[i][j] = 1;
                }else{
                    if(A.charAt(i-1) == B.charAt(j-1) || B.charAt(j-1) == '.'){
                        dp[i][j] = dp[i-1][j-1];
                    }else if(j > 1){
                        int k = j;
                        while(k > 1 && B.charAt(k-1) == '*'){
                            k --;
                        }
                        if(B.charAt(k-1) == A.charAt(i-1) || B.charAt(k-1) == '.'){
                            dp[i][j] = dp[i-1][j];
                        }
                    }
                }
            }
        }
        return dp[A.length()][B.length()];
    }

Can anyone help me? Large test cases are failing. I can’t see anything wrong in my code.


#2

I did not understand your code fully but I think that your missing condition for ‘*’
I am mentioning all the condition for the stars just check weather you have implemented it or not?

if b[current] = ‘*’ and b[prec] != ‘.’ then
if preceding element of b[prec] == a[current] then
1-> either take element of a[curr] then b[curr] can be used again so (i-1,j)
2-> either do not take the b[curr] so (i,j-1);
3-> either do not take both b[prec] and b[curr] so (i,j-2);
else then
do not take both b[prec] and b[curr] so (i,j-2); because you do not have any option