動態規劃解決最長公共子串問題：Java 實現與遞歸優化詳解

問題定義

給定兩個字符串，找出它們共有的最長子串。例："tabcfg" 與 "abckj" 的最長公共子串為 "abc"。

核心思路：問題分解與遞歸關係

設字符串為 a、b：

1. 首字符不同：分別去掉首字符比較，即 a.substring(1) 與 b、b.substring(1) 與 a 比較，最長子串不變。遞歸終止條件：任一字符串為空。
2. 首字符相同：向後逐字符比較，直到第 n 個字符不同。將前 n-1 個字符作為候選子串 c，並遞歸比較 a.substring(1) 與 b、b.substring(1) 與 a，取三者中最長者。

感謝網友 lexy 指出：不能直接丟棄相同前綴繼續比較，必須考慮所有分支，代碼已修正。

Java 實現：備忘錄模式優化遞歸

import java.util.HashMap;
import java.util.Map;

public class CompareStr {
    private Map memo = new HashMap<>();

    public String getLongestString(String str1, String str2) {
        if (isEmpty(str1) || isEmpty(str2)) return "";
        
        String key = str1 + "&&" + str2;
        if (memo.containsKey(key)) return memo.get(key);

        // 計算公共前綴
        char[] c1 = str1.toCharArray();
        char[] c2 = str2.toCharArray();
        int i = 0;
        StringBuilder prefix = new StringBuilder();
        for (; i < c1.length && i < c2.length; i++) {
            if (c1[i] == c2[i]) prefix.append(c1[i]);
            else break;
        }

        String sub1 = str1.substring(i);
        String sub2 = str2.substring(i);
        String result;

        if (i == 0) { // 首字符不同
            String r1 = getLongestString(sub1.substring(1), sub2);
            String r2 = getLongestString(sub1, sub2.substring(1));
            result = r1.length() >= r2.length() ? r1 : r2;
        } else { // 有公共前綴
            String r1 = getLongestString(str1.substring(1), str2);
            String r2 = getLongestString(str1, str2.substring(1));
            String longer = r1.length() > r2.length() ? r1 : r2;
            result = longer.length() >= prefix.length() ? longer : prefix.toString();
        }

        memo.put(key, result);
        return result;
    }

    private boolean isEmpty(String s) {
        return s == null || s.trim().isEmpty();
    }
}

關鍵點解析

• HashMap 備忘錄：以 str1&&str2 為鍵存儲已計算結果，以空間換時間，避免重複計算。
• 遞歸分解完整：涵蓋首字符相同/不同兩大分支，確保不遺漏最優解。
• 可進一步優化：可改用二維 DP 表（dp[i][j] 表示以 s1[i]、s2[j] 結尾的最長公共後綴），時間空間均為 O(mn)，更適合超長字符串。

歡迎大家嘗試優化，或分享更高效的演算法！