字符串操作（编辑距离 · 单词拆分 · 字符串转换）

编辑距离（LeetCode 72）

将 word1 转换为 word2 所需的最少操作数（插入/删除/替换）。

区间 DP：

int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    // 边界：空字符串到任意字符串的编辑距离
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];  // 字符相同，不操作
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],   // 替换
                           Math.min(dp[i - 1][j],             // 删除 word1[i]
                                    dp[i][j - 1]));           // 插入字符到 word1
            }
        }
    }
    return dp[m][n];
}

状态含义：dp[i][j] = word1[0..i-1] 变成 word2[0..j-1] 的最少操作数。

单词拆分（LeetCode 139）

判断字符串能否由字典中的单词拼接：

boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;  // 空字符串可以拆分
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}

优化：用最大单词长度限制内层循环的范围。

字符串解码（LeetCode 394）

3[a2[c]] → accaccacc，用栈：

String decodeString(String s) {
    Deque<Integer> countStack = new ArrayDeque<>();
    Deque<StringBuilder> strStack = new ArrayDeque<>();
    StringBuilder cur = new StringBuilder();
    int k = 0;

    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            k = k * 10 + (c - '0');
        } else if (c == '[') {
            countStack.push(k);
            strStack.push(cur);
            cur = new StringBuilder();
            k = 0;
        } else if (c == ']') {
            int count = countStack.pop();
            StringBuilder prev = strStack.pop();
            String repeated = cur.toString().repeat(count);
            cur = prev.append(repeated);
        } else {
            cur.append(c);
        }
    }
    return cur.toString();
}

翻转字符串中的单词（LeetCode 151）

String reverseWords(String s) {
    String[] words = s.trim().split("\\s+");
    StringBuilder sb = new StringBuilder();
    for (int i = words.length - 1; i >= 0; i--) {
        sb.append(words[i]);
        if (i > 0) sb.append(' ');
    }
    return sb.toString();
}

进阶（O(1) 空间）：先翻转整体，再翻转每个单词。

最长公共子序列（LeetCode 1143）

int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1))
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}