字符串面试题全解析

双指针 (Two Pointers)

双指针在字符串处理中应用极广，包括原地修改、查找子串、反转字符串等。主要分为“同向双指针”（如滑动窗口）和“相向双指针”（如二分查找、回文判断）。

经典案例：反转字符串中的单词 III

题目描述：给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

解题思路：

1. 将字符串转换为字符数组（因为Java/Python中字符串不可变）。
2. 使用两个指针 i 和 j，i 指向单词起始位置，j 寻找单词结束位置（空格）。
3. 对每个单词区间 [i, j) 进行反转。
4. 更新 i = j + 1，继续处理下一个单词。

Python 代码示例：

def reverseWords(s: str) -> str:
    words = s.split(' ')
    reversed_words = [word[::-1] for word in words]
    return ' '.join(reversed_words)
或者使用双指针原地操作
def reverseWordsInPlace(s: str) -> str:
    chars = list(s)
    start = 0
    for end in range(len(chars) + 1):
        if end == len(chars) or chars[end] == ' ':
            # 反转区间 [start, end)
            left, right = start, end - 1
            while left < right:
                chars[left], chars[right] = chars[right], chars[left]
                left += 1
                right -= 1
            start = end + 1
    return ''.join(chars)

动态规划 (Dynamic Programming)

当字符串问题涉及“最长”、“最短”、“是否匹配”且子问题有重叠时，动态规划是首选。关键在于定义状态转移方程。

经典案例：最长回文子串

题目描述：给定一个字符串 s，找到 s 中最长的回文子串。

解题思路（中心扩展法 - 优化版DP思路）：

虽然纯DP需要 O(N^2) 空间，但我们可以利用回文的对称性。以每个字符（或两个字符之间）为中心，向两边扩展，直到字符不相等。这种方法时间复杂度 O(N^2)，空间复杂度 O(1)。

C++ 代码示例：

string longestPalindrome(string s) {
    if (s.empty()) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);     // 奇数长度
        int len2 = expandAroundCenter(s, i, i + 1); // 偶数长度
        int len = max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substr(start, end - start + 1);
}
int expandAroundCenter(const string& s, int left, int right) {
    while (left >= 0 && right < s.length() && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
}