lintcode 581 · 最长重复子序列【中等 vip 动态规划 /递归】

题目

https://www.lintcode.com/problem/581

给出一个字符串，找到最长的重复子序列的长度，并且这两个子序列不能在相同位置有同一元素。
比如：在两个子序列中的第i个元素不能在原来的字符串中有相同的下标。



样例
例1:

输入:"aab"
输出:1
解释:
两个子序列是a（第一个）和a（第二个）。
请注意，b不能被视为子序列的一部分，因为它在两者中都是相同的索引。
例2:

输入:"abc"
输出:0
解释:
没有重复的序列
例3:

输入:"aabb"
输出:2
解释:
有两个相同的子序列"ab". 其中第一个子序列是s[0] + s[2], 第二个子序列是s[1]+s[3], 所以重复子序列的长度为2.
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

思路

和题目最长公共子序列类似。本答案包括递归版本和动态规划版本。
网上搜到的其他答案都是只有动态规划版本，新手根本无法看懂

答案

public class Solution {
    /**
     * @param str: a string
     * @return: the length of the longest repeating subsequence
     */
    public int longestRepeatingSubsequence(String str) {
       if (str == null || str.length() == 0) return 0;
        //  return f1(str); //递归+缓存版本
        return dp(str.toCharArray()); //动态规划版本
    }


    public static int dp(char[] strs) {
        int n = strs.length;
        int[][] dp = new int[n + 1][n + 1];

        //填充第一行
        for (int j = 1; j < n; j++) {
            dp[0][j] = strs[0] == strs[j] ? 1 : dp[0][j - 1];
        }

        //填充第一列
        for (int i = 1; i < n; i++) {
            dp[i][0] = strs[i] == strs[0] ? 1 : dp[i - 1][0];
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                int p1 = dp[i - 1][j];
                int p2 = dp[i][j - 1];
                int p3 = 0;
                p3 += i != j && strs[i] == strs[j] ? (1 + dp[i - 1][j - 1]) : 0;
                dp[i][j] = Math.max(p1, Math.max(p2, p3));
            }
        }

        return dp[n - 1][n - 1];
    }

    public static int f1(String str) {
        char[] strs = str.toCharArray();
        int n = str.length();
        Integer[][] dp = new Integer[n + 1][n + 1];
        return dfs(n - 1, n - 1, strs, dp);
    }

    public static int dfs(int i, int j, char[] strs, Integer[][] dp) {
        if (i >= 0 && j >= 0 && dp[i][j] != null) return dp[i][j];
        if (i == 0 && j == 0) {
            dp[i][j] = 0;
            return 0;
        } else if (i == 0) {
            if (strs[i] == strs[j]) {
                dp[i][j] = 1;
                return 1;

            } else {
                return dfs(i, j - 1, strs, dp);
            }
        } else if (j == 0) {
            if (strs[i] == strs[j]) {
                dp[i][j] = 1;
                return 1;
            } else {
                return dfs(i - 1, j, strs, dp);
            }
        } else {
            int p1 = dfs(i - 1, j, strs, dp);
            int p2 = dfs(i, j - 1, strs, dp);

            int p3 = 0;
            p3 += i != j && strs[i] == strs[j] ? 1 + dfs(i - 1, j - 1, strs, dp) : 0;

            int ans = Math.max(p1, Math.max(p2, p3));

            dp[i][j] = ans;
            return ans;
        }
    }

}
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

本地测试例子

public class LC581 {


    public static int longestRepeatingSubsequence(String str) {
        if (str == null || str.length() == 0) return 0;
        //  return f1(str); //递归+缓存版本
        return dp(str.toCharArray()); //动态规划版本
    }


    public static int dp(char[] strs) {
        int n = strs.length;
        int[][] dp = new int[n + 1][n + 1];

        //填充第一行
        for (int j = 1; j < n; j++) {
            dp[0][j] = strs[0] == strs[j] ? 1 : dp[0][j - 1];
        }

        //填充第一列
        for (int i = 1; i < n; i++) {
            dp[i][0] = strs[i] == strs[0] ? 1 : dp[i - 1][0];
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                int p1 = dp[i - 1][j];
                int p2 = dp[i][j - 1];
                int p3 = 0;
                p3 += i != j && strs[i] == strs[j] ? (1 + dp[i - 1][j - 1]) : 0;
                dp[i][j] = Math.max(p1, Math.max(p2, p3));
            }
        }

        return dp[n - 1][n - 1];
    }

    public static int f1(String str) {
        char[] strs = str.toCharArray();
        int n = str.length();
        Integer[][] dp = new Integer[n + 1][n + 1];
        return dfs(n - 1, n - 1, strs, dp);
    }

    public static int dfs(int i, int j, char[] strs, Integer[][] dp) {
        if (i >= 0 && j >= 0 && dp[i][j] != null) return dp[i][j];
        if (i == 0 && j == 0) {
            dp[i][j] = 0;
            return 0;
        } else if (i == 0) {
            if (strs[i] == strs[j]) {
                dp[i][j] = 1;
                return 1;

            } else {
                return dfs(i, j - 1, strs, dp);
            }
        } else if (j == 0) {
            if (strs[i] == strs[j]) {
                dp[i][j] = 1;
                return 1;
            } else {
                return dfs(i - 1, j, strs, dp);
            }
        } else {
            int p1 = dfs(i - 1, j, strs, dp);
            int p2 = dfs(i, j - 1, strs, dp);

            int p3 = 0;
            p3 += i != j && strs[i] == strs[j] ? 1 + dfs(i - 1, j - 1, strs, dp) : 0;

            int ans = Math.max(p1, Math.max(p2, p3));

            dp[i][j] = ans;
            return ans;
        }
    }


    public static void main(String[] args) {
        System.out.println(longestRepeatingSubsequence("aab")); //1
        System.out.println(longestRepeatingSubsequence("aabb")); //2
        System.out.println(longestRepeatingSubsequence("abc")); //0
        System.out.println(longestRepeatingSubsequence("aaadaaaaaaaaaaabbbbbbbb" +
                "bbbbbbbbbbbmmmmmmmmmmmmmmmdkkkkklkklkldd" +
                "ddddddddddddddddddddddddddddssssssssss" +
                "ssssssssbb"));//100
    }
}
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89