编辑代码

import java.util.ArrayList;
import java.util.Collections;

public class LongestCommonSequence {

    public static int getLongestCommonSequence(String wordA, String wordB, StringBuilder commonSeq) {
        // 1. 构建动态规划表格
        int rowCount = wordA.length() + 1;
        int colCount = wordB.length() + 1;

        int[][] dpArray = new int[rowCount][colCount];

        // 2. 填充动态规划表格
        for (int i = 1; i < rowCount; ++i) {
            for (int j = 1; j < colCount; ++j) {
                if (Character.toUpperCase(wordA.charAt(i - 1)) == Character.toUpperCase(wordB.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]);
                }
            }
        }

        // 3. 找出公共子序列
        int i = rowCount - 1;
        int j = colCount - 1;

        while (i > 0 && j > 0) {
            if (Character.toUpperCase(wordA.charAt(i - 1)) == Character.toUpperCase(wordB.charAt(j - 1))) {
                commonSeq.insert(0, wordA.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];
    }

    public static void main(String[] args) {
        String wordA = "MAGIC";
        String wordB = "magia";
        StringBuilder commonSeq = new StringBuilder();

        int maxLen = getLongestCommonSequence(wordA, wordB, commonSeq);
        System.out.println("The longest common sequence is " + commonSeq + " and its length is " + maxLen);

        wordA = "bowl";
        wordB = "aowt";
        commonSeq.setLength(0); // Clear the StringBuilder
        maxLen = getLongestCommonSequence(wordA, wordB, commonSeq);
        System.out.println("The longest common sequence is " + commonSeq + " and its length is " + maxLen);

        wordA = "sssssgggs";
        wordB = "sgggsssss";
        commonSeq.setLength(0); // Clear the StringBuilder
        maxLen = getLongestCommonSequence(wordA, wordB, commonSeq);
        System.out.println("The longest common sequence is " + commonSeq + " and its length is " + maxLen);
    }
}