Java 字符串算法核心攻略

// 错误：循环里用+拼接，每次都创建新对象，超级慢
String s = "";
for (int i = 0; i < 10000; i++) {
    s += "a"; // O(n²)
}

// 正确：用 StringBuilder
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 10000; i++) {
    sb.append("a"); // O(n)
}
String result = sb.toString();

4. 字符判断

char c = 'a';
Character.isDigit(c); // 是否数字
Character.isLetter(c); // 是否字母
Character.isLetterOrDigit(c); // 判断是否是字母或数字
Character.isLowerCase(c); // 是否小写
Character.toLowerCase(c); // 转小写
'5' - '0'; // 5 - 字符转数字

5. 大小写转换与清理

String s = " Hello World ";
s.toLowerCase(); // " hello world " - 全转小写（判断回文串必用）
s.toUpperCase(); // " HELLO WORLD " - 全转大写
s.trim(); // "Hello World" - 去掉首尾空格（处理输入必用）
s.replaceAll("\\s+", ""); // "HelloWorld" - 去掉所有空格（正则替换）

6. 高级查找与匹配

String s = "hello world";
s.indexOf("world", 6); // 6 - 从指定下标开始查找
s.lastIndexOf('l'); // 9 - 查找字符最后一次出现位置
s.startsWith("he"); // true - 是否以...开头
s.endsWith("ld"); // true - 是否以...结尾
s.matches("[a-z]+"); // true - 正则匹配（判断是否纯字母等）

7. 字符数组的高级操作

char[] chars = {'h', 'e', 'l', 'l', 'o'};

// 数组排序（解决'有效的字母异位词'等题目必用）
java.util.Arrays.sort(chars);

// 数组转字符串后再比较
String sorted = new String(chars);

// 比较两个字符数组是否相等（比转 String 快）
java.util.Arrays.equals(chars1, chars2);

8. 频率统计神器（HashMap/数组）

// 方法 A：使用数组统计（仅限 ASCII 字符，速度最快 O(1) 空间）
int[] count = new int[128]; // 覆盖所有 ASCII 码
count['a']++; // 直接利用 char 自动转 int 特性
count[c]--; // 抵消计数

// 方法 B：使用 HashMap 统计（支持 Unicode/中文，通用但稍慢）
java.util.Map<Character, Integer> map = new java.util.HashMap<>();
map.put(c, map.getOrDefault(c, 0) + 1); // 计数 +1
map.get(c); // 获取某个字符出现的次数
map.containsKey(c); // 判断是否包含该字符

9. 格式化输出（调试与构造必用）

// 类似 Python 的 f-string 或 C 的 printf
String name = "Alice";
int age = 25;
String info = String.format("Name: %s, Age: %d", name, age); // 结果："Name: Alice, Age: 25"

// 常用占位符：
// %s : 字符串
// %d : 整数
// %f : 浮点数
// %c : 字符

二、字符串题型与解题思路

类型 1：哈希表类（字符统计）

核心思想： 用空间换时间，快速查找和统计

什么时候用哈希表？

看到这些关键词就想到哈希表：

• 字符频次、出现次数
• 异位词、字母重排
• 第一个唯一字符
• 两个字符串的映射关系

模板：字符频次统计

// 模板 1：HashMap 统计（适用所有字符）
public Map<Character, Integer> countChars(String s) {
    Map<Character, Integer> map = new HashMap<>();
    for (char c : s.toCharArray()) {
        map.put(c, map.getOrDefault(c, 0) + 1); // 频次 +1
    }
    return map;
}

// 模板 2：数组统计（仅小写字母，更快）
public int[] countCharsArray(String s) {
    int[] count = new int[26]; // 26 个小写字母
    for (char c : s.toCharArray()) {
        count[c - 'a']++; // 'a'映射到 0，'b'映射到 1...
    }
    return count;
}

为什么数组比 HashMap 快？数组直接通过索引访问，HashMap 需要计算哈希值。但数组只适用于字符集有限的情况（如 26 个字母）。

题目 1：有效的字母异位词（LeetCode 242）

题目：判断两个字符串是否是异位词（字母相同但顺序不同）

输入：s = "anagram", t = "nagaram" 输出：true
输入：s = "rat", t = "car" 输出：false

思路：异位词的特点是每个字符出现的次数相同，统计频次后比较即可。

public boolean isAnagram(String s, String t) {
    // 1. 长度不同直接返回 false（异位词长度必须相同）
    if (s.length() != t.length()) return false;

    // 2. 创建数组统计 26 个小写字母的频次
    int[] count = new int[26];

    // 3. 遍历字符串 s，统计每个字符出现的次数
    for (char c : s.toCharArray()) {
        count[c - 'a']++; // 'a'映射到索引 0，'b'映射到索引 1...
    }

    // 4. 遍历字符串 t，每遇到一个字符就将对应计数 -1
    for (char c : t.toCharArray()) {
        count[c - 'a']--; // 如果某个字符的计数变成负数，说明 t 中这个字符比 s 多
        if (count[c - 'a'] < 0) {
            return false;
        }
    }

    // 5. 如果所有字符频次都匹配（都为 0），则是异位词
    return true;
}

为什么这样思考？如果两个字符串是异位词，那么统计完 s 的频次后，遍历 t 应该刚好把所有计数清零。如果某个字符变负数，说明 t 中这个字符比 s 多，不是异位词。

题目 2：字符串中的第一个唯一字符（LeetCode 387）

题目：找出字符串中第一个只出现一次的字符的索引

输入：s = "leetcode" 输出：0（'l'只出现一次）
输入：s = "loveleetcode" 输出：2（'v'是第一个只出现一次的）

思路：先统计每个字符的频次，再遍历一遍找第一个频次为 1 的字符。

public int firstUniqChar(String s) {
    // 1. 创建数组统计 26 个小写字母的频次
    int[] count = new int[26];

    // 2. 第一遍遍历：统计每个字符出现的次数
    for (char c : s.toCharArray()) {
        count[c - 'a']++; // 字符 c 对应的计数 +1
    }

    // 3. 第二遍遍历：按原字符串顺序查找第一个出现次数为 1 的字符
    for (int i = 0; i < s.length(); i++) {
        // 获取当前字符的出现次数
        if (count[s.charAt(i) - 'a'] == 1) {
            return i; // 找到第一个唯一字符，返回其索引
        }
    }

    // 4. 如果没有找到唯一字符，返回 -1
    return -1;
}

为什么要遍历两遍？第一遍统计频次，第二遍按原字符串顺序查找，这样能保证找到的是"第一个"唯一字符。

题目 3：赎金信（LeetCode 383）

题目：判断字符串 ransomNote 能否由字符串 magazine 中的字符构成

输入：ransomNote = "a", magazine = "b" 输出：false
输入：ransomNote = "aa", magazine = "aab" 输出：true

思路：统计 magazine 中每个字符的频次，然后遍历 ransomNote，每用一个字符就减 1，如果不够用就返回 false。

public boolean canConstruct(String ransomNote, String magazine) {
    // 1. 创建数组统计 magazine 中 26 个小写字母的频次
    int[] count = new int[26];

    // 2. 遍历 magazine，统计每个字符的可用数量
    for (char c : magazine.toCharArray()) {
        count[c - 'a']++; // 字符 c 的可用数量 +1
    }

    // 3. 遍历 ransomNote，检查是否有足够的字符可用
    for (char c : ransomNote.toCharArray()) {
        count[c - 'a']--; // 使用一个字符 c，可用数量 -1
        // 如果某个字符的可用数量变成负数，说明 magazine 中这个字符不够用
        if (count[c - 'a'] < 0) {
            return false;
        }
    }

    // 4. 所有字符都够用，可以构成 ransomNote
    return true;
}

为什么这样思考？这题本质上是检查 magazine 是否包含 ransomNote 所需的所有字符（包括数量），用数组统计频次最直接。

类型 2：双指针类

核心思想： 用两个指针从不同位置遍历，避免嵌套循环

什么时候用双指针？

• 回文问题（从两端向中间）
• 反转字符串（交换两端字符）
• 原地修改数组（快慢指针）

模板：对撞指针（判断回文）

public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false; // 两端字符不同，不是回文
        }
        left++; // 左指针右移
        right--; // 右指针左移
    }
    return true; // 所有字符都对称
}

为什么从两端向中间？回文的特点就是对称，从两端比较最直接。时间复杂度 O(n)，空间复杂度 O(1)。

题目 1：验证回文串（LeetCode 125）

题目：判断字符串是否是回文（只考虑字母和数字，忽略大小写）

输入：s = "A man, a plan, a canal: Panama" 输出：true（去掉非字母数字后是"amanaplanacanalpanama"）

思路：用双指针，遇到非字母数字就跳过，比较时忽略大小写。

public boolean isPalindrome(String s) {
    // 1. 初始化双指针：left 指向开头，right 指向末尾
    int left = 0, right = s.length() - 1;

    // 2. 双指针向中间移动
    while (left < right) {
        // 3. 左指针跳过所有非字母数字字符（如空格、标点符号）
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
            left++;
        }

        // 4. 右指针跳过所有非字母数字字符
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
            right--;
        }

        // 5. 比较左右两个字符（转换为小写后比较，忽略大小写）
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
            return false; // 字符不相等，不是回文
        }

        // 6. 两个指针向中间移动
        left++;
        right--;
    }

    // 7. 所有字符都对称，是回文串
    return true;
}

为什么要跳过非字母数字？题目要求只考虑字母和数字，其他字符（空格、标点）都忽略。

题目 2：反转字符串（LeetCode 344）

题目：原地反转字符数组

输入：s = ['h','e','l','l','o'] 输出：['o','l','l','e','h']

思路：用双指针从两端向中间交换字符。

public void reverseString(char[] s) {
    // 1. 初始化双指针：left 指向开头，right 指向末尾
    int left = 0, right = s.length - 1;

    // 2. 双指针向中间移动，交换两端字符
    while (left < right) {
        // 3. 交换 left 和 right 位置的字符
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;

        // 4. 两个指针向中间移动
        left++;
        right--;
    }

    // 5. 交换完成，数组已原地反转
}

为什么这样思考？反转就是把第一个和最后一个交换，第二个和倒数第二个交换…用双指针最直接。

类型 3：滑动窗口类（最重要）

核心思想： 维护一个动态窗口，右指针扩大窗口，左指针收缩窗口

什么时候用滑动窗口？

看到这些关键词就想到滑动窗口：

• 最长/最短子串
• 连续子数组
• 包含某些字符的子串

滑动窗口的两种类型

1. 固定窗口： 窗口大小固定，只需要滑动
2. 可变窗口： 窗口大小动态变化，需要收缩

模板：可变窗口（最常用）

public int slidingWindow(String s) {
    int left = 0, maxLen = 0;
    Set<Character> window = new HashSet<>(); // 维护窗口内的字符

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);

        // 如果窗口内有重复字符，收缩窗口
        while (window.contains(c)) {
            window.remove(s.charAt(left)); // 移除左边界字符
            left++; // 左指针右移
        }

        // 加入右边界字符
        window.add(c);

        // 更新最大长度
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

为什么叫滑动窗口？想象一个窗户在字符串上滑动，窗户里的内容就是当前考虑的子串。右边界不断扩大，左边界根据条件收缩。

题目 1：无重复字符的最长子串（LeetCode 3）

题目：找出字符串中不含重复字符的最长子串的长度

输入：s = "abcabcbb" 输出：3（"abc"）
输入：s = "pwwkew" 输出：3（"wke"）

思路：用 HashSet 维护窗口内的字符，遇到重复字符就收缩窗口。

public int lengthOfLongestSubstring(String s) {
    // 1. 边界条件：空字符串返回 0
    if (s == null || s.length() == 0) return 0;

    // 2. 初始化变量
    int left = 0; // 窗口左边界
    int maxLen = 0; // 记录最长子串长度
    Set<Character> window = new HashSet<>(); // 用 HashSet 存储窗口内的字符

    // 3. 右指针遍历字符串，扩大窗口
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right); // 获取右边界的字符

        // 4. 如果窗口内已有这个字符（重复了），收缩窗口
        while (window.contains(c)) {
            window.remove(s.charAt(left)); // 移除左边界字符
            left++; // 左指针右移，收缩窗口
        }

        // 5. 将右边界字符加入窗口
        window.add(c);

        // 6. 更新最大长度（当前窗口大小 = right - left + 1）
        maxLen = Math.max(maxLen, right - left + 1);
    }

    // 7. 返回最长无重复子串的长度
    return maxLen;
}

为什么要用 HashSet？HashSet 可以 O(1) 时间判断字符是否存在，比遍历数组快得多。

优化版本：用 HashMap 记录字符的索引，遇到重复字符可以直接跳到重复位置的下一个。

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) return 0;
    int left = 0, maxLen = 0;
    Map<Character, Integer> map = new HashMap<>(); // 记录字符最后出现的位置

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);

        // 如果字符已存在且在窗口内，直接跳到重复位置的下一个
        if (map.containsKey(c) && map.get(c) >= left) {
            left = map.get(c) + 1;
        }

        // 更新字符位置
        map.put(c, right);

        // 更新最大长度
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

为什么更快？不需要一个一个移动左指针，直接跳到重复字符的下一个位置。

题目 2：找到字符串中所有字母异位词（LeetCode 438）

题目：找出字符串 s 中所有 p 的异位词的起始索引

输入：s = "cbaebabacd", p = "abc" 输出：[0, 6]
解释：索引 0 的子串"cba"是"abc"的异位词
索引 6 的子串"bac"是"abc"的异位词

思路：固定窗口大小为 p 的长度，滑动窗口，每次检查窗口内的字符频次是否和 p 相同。

public List<Integer> findAnagrams(String s, String p) {
    // 1. 初始化结果列表
    List<Integer> result = new ArrayList<>();

    // 边界条件：s 比 p 短，不可能包含 p 的异位词
    if (s.length() < p.length()) return result;

    // 2. 创建两个数组分别统计 p 和 s 窗口内的字符频次
    int[] pCount = new int[26]; // 统计 p 中每个字符的频次
    int[] sCount = new int[26]; // 统计 s 窗口内每个字符的频次

    // 3. 统计 p 中每个字符的频次
    for (char c : p.toCharArray()) {
        pCount[c - 'a']++;
    }

    // 4. 初始化第一个窗口（长度为 p.length()）
    for (int i = 0; i < p.length(); i++) {
        sCount[s.charAt(i) - 'a']++;
    }

    // 检查第一个窗口是否是异位词
    if (Arrays.equals(pCount, sCount)) {
        result.add(0); // 起始索引 0
    }

    // 5. 滑动窗口：从索引 p.length() 开始遍历
    for (int i = p.length(); i < s.length(); i++) {
        // 窗口右移：加入新字符（右边界）
        sCount[s.charAt(i) - 'a']++;

        // 窗口右移：移除旧字符（左边界）
        sCount[s.charAt(i - p.length()) - 'a']--;

        // 6. 比较当前窗口的字符频次是否和 p 相同
        if (Arrays.equals(pCount, sCount)) {
            // 当前窗口是异位词，记录起始索引
            result.add(i - p.length() + 1);
        }
    }

    // 7. 返回所有异位词的起始索引
    return result;
}

为什么是固定窗口？异位词长度必须和 p 相同，所以窗口大小固定。每次滑动只需要更新边界字符的频次，不需要重新统计整个窗口。

题目 3：字符串的排列（LeetCode 567）

题目：判断 s2 是否包含 s1 的排列（即 s1 的异位词）

输入：s1 = "ab", s2 = "eidbaooo" 输出：true
解释：s2 包含 s1 的排列之一("ba")
输入：s1 = "ab", s2 = "eidboaoo" 输出：false

思路：和上一题类似，固定窗口大小为 s1 的长度，检查窗口内字符频次是否和 s1 相同。

public boolean checkInclusion(String s1, String s2) {
    // 1. 边界条件：s1 比 s2 长，不可能包含 s1 的排列
    if (s1.length() > s2.length()) return false;

    // 2. 创建两个数组分别统计 s1 和 s2 窗口内的字符频次
    int[] s1Count = new int[26]; // 统计 s1 中每个字符的频次
    int[] s2Count = new int[26]; // 统计 s2 窗口内每个字符的频次

    // 3. 统计 s1 中每个字符的频次
    for (char c : s1.toCharArray()) {
        s1Count[c - 'a']++;
    }

    // 4. 初始化第一个窗口（长度为 s1.length()）
    for (int i = 0; i < s1.length(); i++) {
        s2Count[s2.charAt(i) - 'a']++;
    }

    // 检查第一个窗口是否是 s1 的排列
    if (Arrays.equals(s1Count, s2Count)) return true;

    // 5. 滑动窗口：从索引 s1.length() 开始遍历
    for (int i = s1.length(); i < s2.length(); i++) {
        // 窗口右移：加入新字符（右边界）
        s2Count[s2.charAt(i) - 'a']++;

        // 窗口右移：移除旧字符（左边界）
        s2Count[s2.charAt(i - s1.length()) - 'a']--;

        // 6. 比较当前窗口的字符频次是否和 s1 相同
        if (Arrays.equals(s1Count, s2Count)) {
            return true; // 找到 s1 的排列
        }
    }

    // 7. 没有找到 s1 的排列
    return false;
}

为什么这样思考？s1 的排列就是 s1 的异位词，所以问题转化为：s2 中是否存在长度为 s1.length() 的子串，其字符频次和 s1 相同。

类型 4：动态规划类

核心思想： 把问题分解成子问题，避免重复计算

什么时候用动态规划？

• 最长公共子序列/子串
• 最长回文子串
• 编辑距离

题目 1：最长回文子串（LeetCode 5）

题目：找出字符串中最长的回文子串

输入：s = "babad" 输出："bab" 或 "aba"
输入：s = "cbbd" 输出："bb"

思路：回文串的特点是中心对称，从每个可能的中心向两边扩展。

public String longestPalindrome(String s) {
    // 1. 边界条件：空串或单字符直接返回
    if (s == null || s.length() < 2) return s;

    // 2. 初始化变量记录最长回文子串的起始位置和长度
    int start = 0; // 最长回文子串的起始索引
    int maxLen = 0; // 最长回文子串的长度

    // 3. 遍历每个可能的回文中心
    for (int i = 0; i < s.length(); i++) {
        // 情况 1：奇数长度回文（中心是一个字符，如"aba"）
        int len1 = expandAroundCenter(s, i, i);

        // 情况 2：偶数长度回文（中心是两个字符，如"abba"）
        int len2 = expandAroundCenter(s, i, i + 1);

        // 4. 取两种情况中较长的回文长度
        int len = Math.max(len1, len2);

        // 5. 如果当前回文比之前记录的更长，更新结果
        if (len > maxLen) {
            maxLen = len;
            // 计算回文子串的起始位置
            // 公式：i - (len - 1) / 2
            start = i - (len - 1) / 2;
        }
    }

    // 6. 返回最长回文子串
    return s.substring(start, start + maxLen);
}

// 辅助方法：从中心向两边扩展，返回回文长度
private int expandAroundCenter(String s, int left, int right) {
    // 当左右字符相等时，继续向两边扩展
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--; // 左指针左移
        right++; // 右指针右移
    }
    // 返回回文长度（right - left - 1）
    // 注意：循环结束时 left 和 right 已经越界，所以要 -1
    return right - left - 1;
}

为什么要考虑奇数和偶数？回文串可能是奇数长度（如"aba"）或偶数长度（如"abba"），中心不同。

题目 2：回文子串（LeetCode 647）

题目：统计字符串中有多少个回文子串

输入：s = "abc" 输出：3
解释："a", "b", "c"
输入：s = "aaa" 输出：6
解释："a", "a", "a", "aa", "aa", "aaa"

思路：和上一题类似，从每个中心向两边扩展，统计回文子串的数量。

public int countSubstrings(String s) {
    // 1. 初始化计数器
    int count = 0;

    // 2. 遍历每个可能的回文中心
    for (int i = 0; i < s.length(); i++) {
        // 情况 1：奇数长度回文（中心是一个字符）
        count += expandAroundCenter(s, i, i);

        // 情况 2：偶数长度回文（中心是两个字符）
        count += expandAroundCenter(s, i, i + 1);
    }

    // 3. 返回回文子串总数
    return count;
}

// 辅助方法：从中心向两边扩展，返回以该中心为起点的回文子串数量
private int expandAroundCenter(String s, int left, int right) {
    int count = 0; // 记录回文子串数量

    // 当左右字符相等时，继续向两边扩展
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        count++; // 每扩展一次就找到一个新的回文子串
        left--; // 左指针左移
        right++; // 右指针右移
    }

    // 返回以该中心为起点的回文子串数量
    return count;
}

为什么这样思考？每个回文子串都有一个中心，从中心向两边扩展，每扩展一次就找到一个回文子串。

类型 5：栈类

核心思想： 利用栈的后进先出特性处理配对问题

什么时候用栈？

• 括号匹配
• 嵌套结构
• 最近的配对元素

题目 1：有效的括号（LeetCode 20）

题目：判断括号字符串是否有效（每个左括号都有对应的右括号）

输入：s = "()" 输出：true
输入：s = "()[]{}" 输出：true
输入：s = "(]" 输出：false

思路：遇到左括号就入栈，遇到右括号就和栈顶匹配。

public boolean isValid(String s) {
    // 1. 创建栈用于存储左括号
    Stack<Character> stack = new Stack<>();

    // 2. 遍历字符串中的每个字符
    for (char c : s.toCharArray()) {
        // 3. 遇到左括号，入栈
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        }
        // 4. 遇到右括号，和栈顶的左括号匹配
        else {
            // 如果栈为空，说明没有左括号可以匹配
            if (stack.isEmpty()) return false;

            // 弹出栈顶的左括号
            char top = stack.pop();

            // 检查左右括号是否匹配
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }

    // 5. 最后栈应该为空（所有左括号都已匹配）
    return stack.isEmpty();
}

为什么用栈？括号匹配是典型的"最近配对"问题，最近的左括号应该匹配最近的右括号，这正是栈的后进先出特性。

题目 2：简化路径（LeetCode 71）

题目：给定 Unix 风格的绝对路径，简化为规范路径

输入：path = "/home/" 输出："/home"
输入：path = "/../" 输出："/"
输入：path = "/home//foo/" 输出："/home/foo"
输入：path = "/a/./b/../../c/" 输出："/c"

思路：用栈处理路径，遇到".."就弹出栈顶（返回上级目录），遇到"."或空字符串就跳过，其他情况入栈。

public String simplifyPath(String path) {
    // 1. 创建栈用于存储有效的目录名
    Stack<String> stack = new Stack<>();

    // 2. 按"/"分割路径，得到各个部分
    String[] parts = path.split("/");

    // 3. 遍历每个部分
    for (String part : parts) {
        if (part.equals("..")) {
            // 4. 遇到".."表示返回上级目录，弹出栈顶（如果栈不为空）
            if (!stack.isEmpty()) {
                stack.pop();
            }
        } else if (!part.equals(".") && !part.isEmpty()) {
            // 5. 遇到普通目录名（不是"."也不是空字符串），入栈
            // "."表示当前目录，空字符串是多个"/"产生的，都跳过
            stack.push(part);
        }
        // 6. "."和空字符串都不处理，直接跳过
    }

    // 7. 构建结果路径
    if (stack.isEmpty()) return "/";

    StringBuilder sb = new StringBuilder();
    // 遍历栈中的所有目录，拼接成路径
    for (String dir : stack) {
        sb.append("/").append(dir);
    }

    // 8. 返回简化后的路径
    return sb.toString();
}

为什么用栈？路径处理中，".."表示返回上级目录，这是典型的"撤销"操作，用栈的后进先出特性最合适。

三、解题思维框架

看到题目先问自己 3 个问题

1. 这是什么类型的问题？

   • 字符统计、异位词 → 哈希表
   • 子串、子数组 → 滑动窗口
   • 回文、反转 → 双指针
   • 括号匹配 → 栈
   • 最优解 → 动态规划

2. 暴力解法是什么？能优化吗？

   • 先想出暴力解法（通常是嵌套循环）
   • 再想能否用双指针、滑动窗口、哈希表优化

3. 需要什么数据结构？

   • 查找/统计 → HashMap 或数组
   • 动态窗口 → Set 或 Map
   • 配对问题 → Stack

优化路径

暴力 O(n²/n³) ↓ 双指针/滑动窗口 O(n) ↓ 哈希表优化（用空间换时间） ↓ 数组优化（字符集有限时）

四、常见陷阱

1. 字符串不可变

// 错误：循环里拼接字符串
String s = "";
for (int i = 0; i < n; i++) {
    s += "a"; // 每次都创建新对象，O(n²)
}

// 正确：用 StringBuilder
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
    sb.append("a");
}

2. 字符串比较

// 错误：用==比较字符串
if (s1 == s2) {}
// 比较的是引用

// 正确：用 equals()
if (s1.equals(s2)) {}
// 比较的是内容

3. 数组越界

// 注意索引范围
for (int i = 0; i < s.length(); i++) {
    // [0, length)
    char c = s.charAt(i);
}

// substring 是左闭右开
s.substring(0, 3); // [0, 3) 不包含索引 3

4. 边界条件

// 完整的边界检查
if (s == null || s.length() == 0) return 默认值;
if (s.length() == 1) return 特殊处理;

五、刷题路线

入门（10 题）- 先把基础打牢

1. 344 反转字符串 - 双指针入门
2. 242 有效的字母异位词 - 哈希表入门
3. 387 字符串中的第一个唯一字符 - 哈希表统计
4. 125 验证回文串 - 双指针 + 字符判断
5. 28 找出字符串中第一个匹配项的下标 - 字符串匹配
6. 14 最长公共前缀 - 字符串比较
7. 58 最后一个单词的长度 - 字符串遍历
8. 20 有效的括号 - 栈入门
9. 392 判断子序列 - 双指针
10. 383 赎金信 - 哈希表

进阶（15 题）- 掌握核心技巧

11. 3 无重复字符的最长子串 - 滑动窗口经典题
12. 5 最长回文子串 - 中心扩展
13. 49 字母异位词分组 - 哈希表分组
14. 151 反转字符串中的单词 - 字符串处理
15. 438 找到字符串中所有字母异位词 - 固定滑动窗口
16. 567 字符串的排列 - 滑动窗口 + 哈希表
17. 647 回文子串 - 中心扩展变形
18. 205 同构字符串 - 双向映射
19. 290 单词规律 - 哈希表映射
20. 459 重复的子字符串 - KMP 或技巧
21. 680 验证回文字符串 II - 双指针 + 贪心
22. 696 计数二进制子串 - 分组统计
23. 709 转换成小写字母 - 字符处理
24. 771 宝石与石头 - 哈希表查找
25. 819 最常见的单词 - 哈希表统计

六、总结

核心方法速查

// 访问
charAt(i), toCharArray(), substring(start, end)

// 查找
indexOf(), contains()

// 判断
isEmpty(), equals(), startsWith(), endsWith()

// 修改
toLowerCase(), toUpperCase(), trim(), replace()

// 分割拼接
split(), String.join(), StringBuilder.append()

解题三步法

1. 识别题型 - 看关键词选方法
2. 选数据结构 - HashMap/Set/Stack/数组
3. 套模板 - 双指针/滑动窗口/哈希表/栈

记忆口诀

字符统计用哈希 子串问题滑动窗 回文对称双指针 括号配对用栈解

最重要的：先理解思想，再记模板。每道题都问自己"为什么这样做"，而不是死记硬背。