|
| 1 | +packagecom.fishercoder.solutions; |
| 2 | + |
| 3 | +publicclass_1143 { |
| 4 | +publicstaticclassSolution1 { |
| 5 | +/** |
| 6 | + * credit: https://leetcode.com/problems/longest-common-subsequence/solution/ |
| 7 | + * <p> |
| 8 | + * Recall that there are two different techniques we can use to implement a dynamic programming solution; memoization and tabulation. |
| 9 | + * <p> |
| 10 | + * Memoization is where we add caching to a function (that has no side effects). In dynamic programming, it is typically used on recursive functions for a top-down solution that starts with the initial problem and then recursively calls itself to solve smaller problems. |
| 11 | + * Tabulation uses a table to keep track of subproblem results and works in a bottom-up manner: solving the smallest subproblems before the large ones, in an iterative manner. Often, people use the words "tabulation" and "dynamic programming" interchangeably. |
| 12 | + * <p> |
| 13 | + * For most people, it's easiest to start by coming up with a recursive brute-force solution and then adding memoization to it. After that, they then figure out how to convert it into an (often more desired) bottom-up tabulated algorithm. |
| 14 | + */ |
| 15 | +publicintlongestCommonSubsequence(Stringtext1,Stringtext2) { |
| 16 | +if (text1 ==null ||text1.length() ==0 ||text2 ==null ||text2.length() ==0) { |
| 17 | +return0; |
| 18 | + } |
| 19 | +intm =text1.length(); |
| 20 | +intn =text2.length(); |
| 21 | +int[][]dp =newint[m +1][n +1]; |
| 22 | +for (inti =0;i <m;i++) { |
| 23 | +for (intj =0;j <n;j++) { |
| 24 | +dp[i][j] = -1; |
| 25 | + } |
| 26 | + } |
| 27 | +returntopDownRecursiveSolve(dp,0,0,text1,text2); |
| 28 | + } |
| 29 | + |
| 30 | +privateinttopDownRecursiveSolve(int[][]dp,inti,intj,Stringtext1,Stringtext2) { |
| 31 | +if (dp[i][j] != -1) { |
| 32 | +returndp[i][j]; |
| 33 | + } |
| 34 | +//option1: we don't include text1.charAt(i) in the optimal solution |
| 35 | +intoption1 =topDownRecursiveSolve(dp,i +1,j,text1,text2); |
| 36 | +//option2: we do include text1.charAt(i) in the optimal solution as long as a match in text2 at or after j does exist |
| 37 | +intfirstOccurence =text2.indexOf(text1.charAt(i),j); |
| 38 | +intoption2 =0; |
| 39 | +if (firstOccurence != -1) { |
| 40 | +option2 =1 +topDownRecursiveSolve(dp,i +1,firstOccurence +1,text1,text2); |
| 41 | + } |
| 42 | +dp[i][j] =Math.max(option1,option2); |
| 43 | +returndp[i][j]; |
| 44 | + } |
| 45 | + } |
| 46 | +} |