动态规划 最长公共子序列

实现原理来自于https://blog.csdn.net/hrn1216/article/details/51534607
采用动态规划求得最大公共子序列的长度 根据dp数组进行递归反推到相等节点

import java.util.*;

public class Solution {

public static void main(String[] args) {
    String str = LCS("1A2C3D4B56", "B1D23CA45B6A");
    System.out.println(str);
}

/**
 * longest common subsequence
 * 
 * @param s1
 *            string字符串 the string
 * @param s2
 *            string字符串 the string
 * @return string字符串
 */
public static String LCS(String s1, String s2) {
    char[] cs1 = s1.toCharArray();
    char[] cs2 = s2.toCharArray();

    int[][] dp = new int[s1.length() + 1][s2.length() + 1];
    for (int i = 0; i < dp.length; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j < dp[0].length; j++) {
        dp[0][j] = 0;
    }
    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            if (cs1[i - 1] == cs2[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]);
            }
        }
    }
    int len = dp[s1.length()][s2.length()];
    char[] lcs = new char[len];
    createLCS(cs1, cs2, dp, s1.length(), s2.length(), lcs, len);
    return new String(lcs);
}

public static void createLCS(char[] cs1, char[] cs2, int[][] dp, int x, int y, char[] lcs, int len) {
    if (x < 1 || y < 1 || len < 0) {
        return;
    }
    if (cs1[x - 1] == cs2[y - 1]) {
        lcs[--len] = cs1[x - 1];
        // 如果相等来源于左上角元素
        createLCS(cs1, cs2, dp, x - 1, y - 1, lcs, len);
    } else {
        if (dp[x][y] == dp[x][y - 1]) {// 不相等来源于左边
            createLCS(cs1, cs2, dp, x, y - 1, lcs, len);
            return;
        }
        if (dp[x][y] == dp[x - 1][y]) {// 不相等来源于上边
            createLCS(cs1, cs2, dp, x - 1, y, lcs, len);
            return;
        }
    }
}

/**
 * longest common subsequence
 * 
 * @param s1
 *            string字符串 the string
 * @param s2
 *            string字符串 the string
 * @return string字符串
 */
public static int LCSLength(String s1, String s2) {
    char[] cs1 = s1.toCharArray();
    char[] cs2 = s2.toCharArray();
    int[][] dp = new int[s1.length() + 1][s2.length() + 1];
    for (int i = 0; i < dp.length; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j < dp[0].length; j++) {
        dp[0][j] = 0;
    }
    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            if (cs1[i - 1] == cs2[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[s1.length()][s2.length()];
}

}