【过时】2021/1/29 最长公共子序列

最长公共子序列

http://www.nowcoder.com/questionTerminal/6d29638c85bb4ffd80c020fe244baf11

题目描述

给定两个字符串str1和str2，输出连个字符串的最长公共子序列。如过最长公共子序列为空，则输出-1。

示例

输入

"1A2C3D4B56","B1D23CA45B6A"

返回值

"123456"

说明

"123456"和“12C4B6”都是最长公共子序列，任意输出一个。

解题思路

相信做完《NC91 最长递增子序列》的胖友们会很容易看懂解题思路，接下来可能会讲的有点抽象，偶尽量图解，没做过的胖友建议先去试一试。（虽然NC91也有亿点抽象）

动态规划问题中的老办法，就是看输入值，如果有两个或以上的输入值，那就首先考虑用二维数组对付他，在很多题目都很有效，我们这里就借用上面的例子来演示。二维数组 dp 的纵轴 i 设为 str1，横轴 j 设为 str2，dp 中的元素表示 str1 第 i 个字符与 str2 第 j 个字符一致。

圆圈表示 str1 在这一行的 j 位置找到了和 str2 里一样的字符。
为了看的更清楚一些，我们画几条线将它们连起来。

我们可以看到 str1 中有一个字符 B，而 str2中有两个，这里我们为了方便看到，用粗线标出。
这并不是我们想要的，我们想要的一一对应应该是按照顺序来的，尽管它有多个相同的字符，如下图。

这才是我们要的一一对应的效果嘛。
假设我们已经从（1）中获得了“圈圈”标记好的二维数组了，接下来我们该给这些“圈圈”标上数字了。（如果胖友们看不懂为什么要这样做，请先坚持下去，跟着思路走，最后解释清楚再倒回来看）
标数字的准则是：纵轴上与自己上面的圈圈比较，在横轴则比较自己圈圈的位置和其他圈圈的位置，自己右邻圈圈的值赋给自己，如果自己就是最右边的圈圈，那就从左边那边拿最大值再 +1。

图1

图2

图3

图4

图5

上面的图请胖友们自己在纸上画一画，顺序从上到下，规则是当前画到这一行的圈圈和上一行的圈圈作比较，如果当前行的圈圈在上一行圈圈的右边，那就在上面所有的圈圈里找一个最大值再 +1，否则在上面所有圈圈中无视找一个在右边离自己最近（无视纵轴深度）的圈圈复制值。

现在我们已经标完号了。现在我们从右往左，从下到上，标号从大到小获取字符吧！

获得对应的值 [1, 2, 3, 4, 5, 6]，也就是上面示例给出的返回值。至此我们算出了答案。
抛开上面的操作，我们整理一下我们刚才到底做了什么。
- 首先，我们建立了一个用于标号的数组 temp。在遍历由 str1 和 str2 组成的二维数组 arr 时，当前遍历到的字符 arr[i][j] 的横坐标 j 需要存储进 temp，如果 j 比 temp 中最后一个元素值大，那么就直接将 j 存到 temp 最后。如果 j 比 temp 最后一个元素值小，那么就从 temp 中找到第一个比 j 大的值，然后用 j 替换它。j 所存放在 temp 的位置就是标号，将标号存放在 nums 数组的 nums[j] 中，便于最后执行像上面的操作，从右到左，从下到上，标号从大到小进行遍历。
- 然后我们思考一下为什么要这么存放？其实 j 是 str2 的索引，只要将标号存放在 nums[j]，就可以根据 j 获得 str2 在 j 中的字符及其对应的标号。
- 为何这样就可以标号？其实胖友们只要自己动手画一下 temp 数组的存储过程就可以发现，二维数组 arr 的每次遍历其实都是动态规划中的子问题，每遍历一次子问题就扩大一次，当前遍历到的“圈圈”其实是当前子问题中，如果算上自己这个“圈圈”，那么公共子串长度是多少。
最后，要记得元素“一一对应”，方法有很多，我这里用的是 Map 记录重复元素的个数来实现一一对应。

Java代码实现

！！！思路是对的但代码错了，别看，我要脸！！！
@Deprecated

public class Solution {
    public String LCS (String s1, String s2) {
        // 为了方便阅读，这里把“无公共子序列则返回-1”的代码删掉
        int rowLen = s1.length();
        int colLen = s2.length();
        // 字典
        int[] nums = new int[rowLen];
        // 临时存储便于标号
        int[] temp = new int[colLen + 1];
        int tempIndex = 0;
        // 记录重复字符个数
        HashMap<Character, Integer> map = new HashMap<Character, Integer>(colLen);

        for (int i = 0; i < rowLen; ++i) {
            if (i==7) {
                System.out.println();
            }
            int charNum = 0;
            if (map.containsKey(s1.charAt(i))) {
                charNum = map.get(s1.charAt(i));
            }
            for (int j = 0; j < colLen; ++j) {
                char currentChar = s2.charAt(j);
                if (s1.charAt(i) == currentChar) {
                    // 去重
                    if (charNum > 0) {
                        --charNum;
                        continue;
                    }
                    if (j > temp[tempIndex]) {
                        ++tempIndex;
                        temp[tempIndex] = j;
                        nums[i] = tempIndex;
                        map.put(currentChar, charNum + 1);
                    } else {
                        int index = findFirstGreater(temp, tempIndex, j);
                        temp[index] = j;
                        nums[i] = index;
                    }
                    break;
                }
            }
        }

        char[] res = new char[tempIndex];
        for(int i = nums.length - 1; i > 0; --i) {
            if (nums[i] == tempIndex) {
                res[tempIndex - 1] = s1.charAt(i);
                --tempIndex;
            }
        }
        return new String(res);
    }

    private int findFirstGreater(int[] temp, int len, int source) {
        // 找第一个比 source 大的数
        int left = 1, right = len;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (source <= temp[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}