Top Down Approach(JAVA)


#1
public class Solution {
    int dp[][];
    public int anytwo(String A) {
        dp=new int[A.length()][A.length()];
        for(int i=0;i<dp.length;i++)
        Arrays.fill(dp[i],-1);
        int val=f(A,0,1);
        if(val>=2)
        return 1;
        else
        return 0;
    }
    
    int f(String a,int i,int j){
        if(i>=a.length() || j>=a.length())
        return 0;
        if(dp[i][j]!=-1)
        return dp[i][j];
        int result=0;
        if(a.charAt(i)==a.charAt(j)){  // skipping current character on both string by adding 1 in ans
            result=Math.max(1+f(a,i+1,j+1),result);
        }
        else{     //  skipping current character of second string OR skipping current character in both String without adding 1 in result
            result=Math.max(f(a,i,j+1),Math.max(f(a,i+1,j+1),result));
        }
        return dp[i][j]=result;
    }
    
}