题解 | #最长公共子序列(一)#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * s1和s2最长公共子序列的长度
     * @param s1 string字符串
     * @param s2 string字符串
     * @return int整型
     */
    public int LCS (String text1, String text2) {
        // write code here
        char[] maxStr = text1.length() >= text2.length() ? text1.toCharArray() : text2.toCharArray();
        char[] minStr = text1.length() < text2.length() ? text1.toCharArray() : text2.toCharArray();
        int N = maxStr.length;
        int M = minStr.length;
        int[][] dp = new int[2][M + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (maxStr[i - 1] == minStr[j - 1]) {
                    dp[i % 2][j] = dp[(i + 1) % 2][j - 1] + 1;
                } else {
                    dp[i % 2][j] = Math.max(dp[(i + 1) % 2][j], dp[i % 2][j - 1]);
                }
            }
        }
        return dp[N % 2][M];
    }
}