编辑代码

package homework;
import java.util.Arrays;

public class CommonStringSequence {
    public static void main(String[] args) {
        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 its 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 its 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 its length is " + maxLen);
    }

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

        int rowCount = wordA.length() + 1;
        int colCount = wordB.length() + 1;

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

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

        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) {
                if (upperWordA.charAt(i - 1) == upperWordB.charAt(j - 1)) {
                    dpArray[i][j] = 1 + dpArray[i - 1][j - 1];
                } else {
                    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;
            }
        }

        return dpArray[rowCount - 1][colCount - 1];
    }
}