跳到主要内容

字符串

问题​

Java 中字符串相关的常见算法题有哪些？

答案​

反转字符串（LeetCode 344）​

双指针原地反转
public 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;
    }
}

最长回文子串（LeetCode 5）​

中心扩展法 O(n²)
public String longestPalindrome(String s) {
    int start = 0, maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        // 奇数长度回文和偶数长度回文都要尝试
        int len1 = expand(s, i, i);       // 奇数：以 i 为中心
        int len2 = expand(s, i, i + 1);   // 偶数：以 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;
}

字符串相加（LeetCode 415）​

模拟竖式加法
public String addStrings(String num1, String num2) {
    StringBuilder sb = new StringBuilder();
    int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry > 0) {
        int a = i >= 0 ? num1.charAt(i--) - '0' : 0;
        int b = j >= 0 ? num2.charAt(j--) - '0' : 0;
        int sum = a + b + carry;
        sb.append(sum % 10);
        carry = sum / 10;
    }
    return sb.reverse().toString();
}

KMP 算法（LeetCode 28）​

KMP 字符串匹配
public int strStr(String haystack, String needle) {
    int[] next = buildNext(needle);
    int i = 0, j = 0;
    while (i < haystack.length()) {
        if (haystack.charAt(i) == needle.charAt(j)) {
            i++;
            j++;
        } else if (j > 0) {
            j = next[j - 1];  // 利用 next 数组回退
        } else {
            i++;
        }
        if (j == needle.length()) return i - j;
    }
    return -1;
}

// 构建 next 数组（前缀表）
private int[] buildNext(String pattern) {
    int[] next = new int[pattern.length()];
    int len = 0, i = 1;
    while (i < pattern.length()) {
        if (pattern.charAt(i) == pattern.charAt(len)) {
            next[i++] = ++len;
        } else if (len > 0) {
            len = next[len - 1];
        } else {
            next[i++] = 0;
        }
    }
    return next;
}
KMP 核心思想

当匹配失败时，不回退文本指针 i，而是利用模式串的最长公共前后缀（next 数组）跳过已匹配的部分，时间复杂度 O(m+n)O(m + n)。

判断回文串（LeetCode 125）​

双指针跳过非字母数字
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;
}

常见面试问题​

Q1: String、StringBuilder、StringBuffer 的区别？​

答案：

详见 String 深入。算法题中拼接字符串必须用 StringBuilder，避免 String + 在循环中产生大量中间对象。

Q2: KMP 的时间复杂度？​

答案：

  • 构建 next 数组：O(m)O(m)
  • 匹配过程：O(n)O(n)
  • 总计：O(m+n)O(m + n)，远优于暴力法 O(m×n)O(m \times n)

Q3: 字符串题目常见技巧？​

答案：

技巧适用题目
双指针反转、回文判断
滑动窗口最小覆盖子串、无重复最长子串
哈希表计数异位词、字符频率
中心扩展回文子串
KMP字符串匹配

相关链接​