It’s not on the LeetCode, but on the LintCode.

LintCode link

first thought

  • Use DP, build a matrix dp to represent the maximum number with the substring of a and b.
  • If the current chars(a[i], b[j])are equal, the value of current is the value of last position + 1. dp[i][j] = dp[i - 1][j - 1] + 1;
  • If a[i] == b[j - 1], dp[i][j] = dp[i - 1][j - 2] + 1;
  • If a[i - 1] == b[j], dp[i][j] = dp[i - 2][j - 1] + 1;
  • If not the same, just copy the value of the previous one.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution {
    /*
     * @param A: A string
     * @param B: A string
     * @return: The length of longest common subsequence of A and B
     */
    public int longestCommonSubsequence(String A, String B) {
        // write your code here
        if (A == null || B == null) {
            return 0;
        }
        char[] charA = A.toCharArray();
        char[] charB = B.toCharArray();
        int na = charA.length;
        int nb = charB.length;
        int[][] dp = new int[na + 1][nb + 1];
        for (int i = 0; i <= na; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i <= nb; i++) {
            dp[0][i] = 0;
        }
        for (int i = 1; i<= na; i++) {
            for (int j = 1; j <= nb; j++) {
                if (charA[i - 1] == charB[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else if (j > 1 && charA[i - 1] == charB[j - 2]) {
                    dp[i][j] = dp[i - 1][j - 2] + 1;
                } else if (i > 1 && charA[i - 2] == charB[j - 1]) {
                    dp[i][j] = dp[i - 2][j - 1] + 1;
                } else {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[na][nb];
    }
};

problem

WA.

reason

A completely confused solution.

rethink

  • If they’re the same, just plus 1.
  • If they are not the same. It’s the maximum length between dp[i][j - 1] and dp[i - 1][j].

modification

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
    /*
     * @param A: A string
     * @param B: A string
     * @return: The length of longest common subsequence of A and B
     */
    public int longestCommonSubsequence(String A, String B) {
        // write your code here
        if (A == null || B == null) {
            return 0;
        }
        char[] charA = A.toCharArray();
        char[] charB = B.toCharArray();
        int na = charA.length;
        int nb = charB.length;
        int[][] dp = new int[na + 1][nb + 1];
        for (int i = 0; i <= na; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i <= nb; i++) {
            dp[0][i] = 0;
        }
        for (int i = 1; i<= na; i++) {
            for (int j = 1; j <= nb; j++) {
                if (charA[i - 1] == charB[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[na][nb];
    }
};