🟡 剑指 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];    }}