字符串：高频面试题型全解

一、字符串基础

字符串是由字符组成的有限序列，是面试中出现频率最高的数据类型之一。

Java 中的字符串

类	特点	适用场景
`String`	不可变	少量操作
`StringBuilder`	可变，非线程安全	频繁拼接
`StringBuffer`	可变，线程安全	多线程拼接

面试必知：Java String 不可变，每次修改都创建新对象。频繁修改必须用 StringBuilder。

常用操作复杂度

操作	String	StringBuilder

public 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;
}

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

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

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }
    for (int c : count) {
        if (c != 0) return false;
    }
    return true;
}

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    int[] need = new int[26], window = new int[26];
    for (char c : p.toCharArray()) need[c - 'a']++;

    int left = 0, valid = 0;
    for (int right = 0; right < s.length(); right++) {
        int r = s.charAt(right) - 'a';
        window[r]++;
        if (window[r] <= need[r]) valid++;

        if (right - left + 1 > p.length()) {
            int l = s.charAt(left) - 'a';
            if (window[l] <= need[l]) valid--;
            window[l]--;
            left++;
        }
        if (valid == p.length()) res.add(left);
    }
    return res;
}

public 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];
}

public 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], dp[i][j - 1]));
            }
        }
    }
    return dp[m][n];
}

技巧	场景	示例
双指针	回文、反转	验证回文串
滑动窗口	子串问题	最小覆盖子串
字符计数	异位词、频率	26 位数组
DP	子序列、编辑距离	LCS、编辑距离
哈希	快速查找	罗马数字转整数
StringBuilder	高效拼接	字符串压缩

public String compress(String s) {
    StringBuilder sb = new StringBuilder();
    int count = 1;
    for (int i = 1; i <= s.length(); i++) {
        if (i < s.length() && s.charAt(i) == s.charAt(i - 1)) {
            count++;
        } else {
            sb.append(s.charAt(i - 1));
            if (count > 1) sb.append(count);
            count = 1;
        }
    }
    return sb.length() < s.length() ? sb.toString() : s;
}

拼接	O(n)（新建对象）	O(1) 均摊
charAt(i)	O(1)	O(1)
substring	O(n)（Java 7+）	—
indexOf	O(nm)	O(nm)

字符串：高频面试题型全解

一、字符串基础

Java 中的字符串

常用操作复杂度

字符串基础 String Basics

一、字符串基础

Java 中的字符串

常用操作复杂度

字符串基础 String Basics

二、经典题型分类

三、回文问题

3.1 验证回文串

3.2 最长回文子串（中心扩展法）

四、字符统计与异位词

4.1 有效异位词

4.2 找所有异位词（滑动窗口）

五、子串与子序列

5.1 最长公共子序列（LCS）

5.2 编辑距离

六、字符串常用技巧

字符串压缩

七、面试常见题

八、调试技巧

相关教程