🟡 剑指 Offer II 095. 最长公共子序列
LeetCode 提示
题目难度 中等
原题链接 🔗 leetcode
#
题解1听说是用二维动态规划的经典例题,孤陋寡闻了。
class Solution { public int longestCommonSubsequence(String text1, String text2) { int n1 = text1.length(), n2 = text2.length(); int[][] matrix = new int[n1+1][n2+1];
for (int i=1; i<=n1; i+=1) { for (int j=1; j<=n2; j+=1) { if (text1.charAt(i-1) == text2.charAt(j-1)) { matrix[i][j] = matrix[i-1][j-1] + 1; } else { matrix[i][j] = Math.max(matrix[i-1][j], matrix[i][j-1]); } } }
return matrix[n1][n2]; }}
#
题解2照旧有优化空间。只需要考虑相邻的两排即可。当然看到更加优化的是只考虑相邻两项+单排即可,但这样写代码的逻辑又太绕了。
class Solution { public int longestCommonSubsequence(String text1, String text2) { int n1 = text1.length(), n2 = text2.length(); int[][] matrix = new int[2][n2+1]; int lastRowIdx = 0;
for (int i=1; i<=n1; i+=1) { for (int j=1; j<=n2; j+=1) { if (text1.charAt(i-1) == text2.charAt(j-1)) { matrix[1-lastRowIdx][j] = matrix[lastRowIdx][j-1] + 1; } else { matrix[1-lastRowIdx][j] = Math.max(matrix[lastRowIdx][j], matrix[1-lastRowIdx][j-1]); } } lastRowIdx = 1-lastRowIdx; }
return matrix[lastRowIdx][n2]; }}