字符串：经典算法与内存语义

字符串基础操作

// Java 常用 API
s.length()               // 长度
s.charAt(i)              // 第i个字符
s.substring(l, r)        // 子串 [l, r)
s.indexOf("ab")          // 查找子串
s.contains("ab")         // 是否包含
s.replace("a", "b")      // 替换
s.split(" ")             // 分割
s.toCharArray()          // 转字符数组
s.toLowerCase() / s.toUpperCase()
String.valueOf(arr)      // 字符数组转字符串
new StringBuilder(s).reverse().toString()  // 反转

双指针与反转

反转字符串

void reverseString(char[] s) {
    int left = 0, right = s.length - 1;
    while (left < right) {
        char tmp = s[left]; s[left] = s[right]; s[right] = tmp;
        left++; right--;
    }
}

反转单词（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();
}

回文问题

验证回文串（LeetCode 125）

boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right)))
            return false;
        left++; right--;
    }
    return true;
}

最长回文子串（LeetCode 5）

中心扩展法：从每个字符（或每对相邻字符）向两侧扩展：

String longestPalindrome(String s) {
    int start = 0, maxLen = 1;
    for (int i = 0; i < s.length(); i++) {
        int odd = expand(s, i, i);         // 奇数长度
        int even = expand(s, i, i + 1);    // 偶数长度
        int len = Math.max(odd, even);
        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;
        }
    }
    return s.substring(start, start + maxLen);
}

int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    return r - l - 1;
}

回文子串数量（LeetCode 647）

同样中心扩展，累计每次扩展成功的次数：

int countSubstrings(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        count += countExpand(s, i, i);       // 奇数回文
        count += countExpand(s, i, i + 1);   // 偶数回文
    }
    return count;
}

int countExpand(String s, int l, int r) {
    int count = 0;
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        count++; l--; r++;
    }
    return count;
}

字符串匹配（KMP 算法）

KMP 避免了暴力匹配 O(n·m) 的重复扫描，通过预计算"部分匹配表"（next 数组）实现 O(n+m)。

int[] buildNext(String pattern) {
    int m = pattern.length();
    int[] next = new int[m];  // next[i] = 模式串前 i+1 个字符的最长前后缀长度
    int k = 0;                 // 当前最长前后缀匹配长度
    for (int i = 1; i < m; i++) {
        while (k > 0 && pattern.charAt(i) != pattern.charAt(k)) k = next[k - 1];
        if (pattern.charAt(i) == pattern.charAt(k)) k++;
        next[i] = k;
    }
    return next;
}

int kmpSearch(String text, String pattern) {
    int[] next = buildNext(pattern);
    int n = text.length(), m = pattern.length();
    int k = 0;  // 已匹配的 pattern 字符数
    for (int i = 0; i < n; i++) {
        while (k > 0 && text.charAt(i) != pattern.charAt(k)) k = next[k - 1];
        if (text.charAt(i) == pattern.charAt(k)) k++;
        if (k == m) return i - m + 1;  // 匹配成功，返回起始位置
    }
    return -1;
}

实际工程：Java 中常用 s.indexOf(p) 替代（底层实现类似 BM 算法）。但理解 KMP 的思想（利用已知匹配信息避免回退）非常重要。

字符串变换问题

字母异位词分组（LeetCode 49）

List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] key = s.toCharArray();
        Arrays.sort(key);                         // 排序后的字符串作为键
        map.computeIfAbsent(new String(key), k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

有效括号（LeetCode 20）

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') stack.push(c);
        else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{'))
                return false;
        }
    }
    return stack.isEmpty();
}

最长公共前缀（LeetCode 14）

String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
        while (!strs[i].startsWith(prefix)) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }
    }
    return prefix;
}

常见字符串题型速查