educative.io

Getting wrong answer with below approach, why?


#1
public static int lengthofLongestCommonSubsequenceOtherWayDPTB(String input1, String input2) {
	int index1 = 0, index2 = 0, currentLength = 0;
	Integer[][] dp = new Integer[input1.length()][input2.length()];
	int length = lengthofLongestCommonSubsequenceOtherWayDPTB(input1.toCharArray(), input2.toCharArray(), index1, index2,
			currentLength, dp);
	return length;
}

private static int lengthofLongestCommonSubsequenceOtherWayDPTB(char[] input1, char[] input2, int index1,
		int index2, int currentLength, Integer[][] dp) {

	if (index1 >= input1.length) {
		return currentLength;
	}

	if (index2 >= input2.length) {
		return currentLength;
	}

	if (dp[index1][index2] != null) {
		return dp[index1][index2];
	}

	if (input1[index1] == input2[index2]) {
		dp[index1][index2] =lengthofLongestCommonSubsequenceOtherWayDPTB(input1, input2, index1 + 1, index2 + 1, currentLength+1, dp);
	}

	else {
		dp[index1][index2] = max(lengthofLongestCommonSubsequenceOtherWayDPTB(input1, input2, index1, index2 + 1, currentLength, dp),
				lengthofLongestCommonSubsequenceOtherWayDPTB(input1, input2, index1 + 1, index2, currentLength, dp));
	}

	return dp[index1][index2];

}