编辑代码

import java.util.Arrays;

public class CommonStringSequence {
    public static int getLongestCommonSequence(String wordA, String wordB, StringBuffer sBuffer) {

        // 1. 确定子问题，构建动态规划表
        int rowCount = wordA.length() + 1;
        int colCount = wordB.length() + 1;

        String upperWordA = wordA.toUpperCase();
        String upperWordB = wordB.toUpperCase();

        if (0 == wordA.length() || 0 ==  wordB.length()) {
            System.out.println("Please check word you entered." );
            return 0;
        }

        // 2. 创建表格，横轴是字符串A，纵轴是字符串B
        int[][] dpArray = new int[rowCount][colCount];
        for (int i = 0; i < rowCount; ++i) {
            Arrays.fill(dpArray[i], 0);
        }


        // 填充表格
        for (int i = 1; i < rowCount; ++i)
        {
            for (int j = 1; j < colCount; ++j)
            {
                // 字符串A的i位置的字符和字符串B的j位置的字符相等
                if (upperWordA.charAt(i-1) == upperWordB.charAt(j-1)) {
                    // 记录下相等的公共子序列长度为1,如果去掉相等的字符后，还有剩余的子串，加上子串的最长公共子序列
                    dpArray[i][j] = 1 + dpArray[i - 1][j - 1];

                }
                else {
                    // 字符串A的i位置的字符和字符串B的j位置的字符不相等
                    // 1. 子串可以是去掉字符串A的i位置的字符子串和字符串B到j位置的子串
                    // 2. 子串也可以使去掉字符串B的j位置的字符和字符串A到i位置的子串
                    // 选取较大的最大公共子序列长度
                    dpArray[i][j] = Math.max(dpArray[i - 1][j], dpArray[i][j - 1]);
                }

            }
        }

        // 找出公共子序列
        int i = rowCount - 1;
        int j = colCount - 1;
        while(i > 0 && j > 0) {
            if (upperWordA.charAt(i-1) == upperWordB.charAt(j-1)) {
                sBuffer.insert(0, upperWordA.charAt(i-1));
            }

            if (dpArray[i - 1][j] > dpArray[i][j - 1]) {
                i = i - 1;
            }
            else if (dpArray[i - 1][j] < dpArray[i][j - 1]){
                j = j - 1;
            }
            else {
                i = i - 1;
                j = j - 1;
            }
        }

        // 表格的最后一格就是字符串A和字符串B的最长公共子序列的长度
        return dpArray[rowCount - 1][colCount - 1];
    }

    public static void test() {
        String wordA = "MIGRATION";
        String wordB = "Migratipn";
        StringBuffer sBuffer = new StringBuffer("");

        int maxLen = getLongestCommonSequence(wordA, wordB, sBuffer);
        System.out.println("The longest common sequence is " + sBuffer + " and it's length is " + maxLen);

        wordA = "Fish";
        wordB = "Hist";
        sBuffer.delete(0, maxLen);

        maxLen = getLongestCommonSequence(wordA, wordB, sBuffer);
        System.out.println("The longest common sequence is " + sBuffer + " and it's length is " + maxLen);

        wordA = "HHHHHTTTH";
        wordB = "HTTTHHHHH";
        sBuffer.delete(0, maxLen);

        maxLen = getLongestCommonSequence(wordA, wordB, sBuffer);
        System.out.println("The longest common sequence is " + sBuffer + " and it's length is " + maxLen);


    }

    public static void main(String[] args) {
        CommonStringSequence.test();
    }
}