1143. Longest Common Subsequence

Problem Statement

Pattern:

---

Solution

Integer[][] cache;
public int longestCommonSubsequence(String text1, String text2) {
		cache = new Integer[text1.length()+1][text2.length()+1];
		return dp(text1.toCharArray(), text2.toCharArray(), text1.length()-1, text2.length()-1);
}
 
public int dp(char[] t1, char[] t2, int n1, int n2) {
	if(n1 < 0 || n2 < 0) return 0;
	if(cache[n1][n2]!=null) return cache[n1][n2];
	
	if(t1[n1] == t2 [n2])  return cache[n1][n2] = dp(t1, t2, n1-1, n2-1) + 1;
	
	return cache[n1][n2] = Math.max(
		dp(t1, t2, n1-1, n2), dp(t1, t2, n1, n2-1)
	);
	
}~

TC : $n\ast m$ SC : $n\ast m$