概述为什么字符串是算法题里的高频主角学完数组之后字符串通常就是下一站。原因并不复杂很多题目的输入本质上就是一段文本字符串底层往往和数组处理思路高度相似双指针、哈希表、滑动窗口、KMP 等经典算法很多都和字符串密切相关面试中非常喜欢考察字符串因为它能同时检验遍历能力、边界处理能力和代码细节能力这篇文章的目标不是单纯讲String的语法而是帮助你建立字符串题最基础的 4 种意识字符串本质上也是一种可遍历的数据序列字符统计类问题通常围绕“计数”展开字符串反转类问题通常围绕“双指针”展开字符匹配类问题通常围绕“比较、扫描、定位”展开学完这篇你应该能看懂大多数基础字符串题到底在考什么。核心概念字符串到底是什么字符串可以理解为由多个字符按顺序组成的一段文本数据。例如Stringsalgorithm;这里的s就是一个字符串它由多个字符依次组成a l g o r i t h m如果从算法角度看字符串和数组非常像都可以按位置访问元素都可以从头到尾遍历都经常会用到下标都很依赖边界判断不同点在于字符串处理的对象是字符而不是普通整数。在 Java 中如果你想访问字符串中的某个字符最常见的方式是Stringshello;charchs.charAt(1);// e字符串长度则通过length()获取intns.length();原理字符串题为什么特别考验细节数组题里很多元素比较的是数值大小而字符串题里除了遍历你还会频繁遇到这些问题当前字符是不是字母是否和另一个字符相等大小写是否要统一空格和标点是否需要跳过比较的是字符、子串还是整个字符串所以字符串题经常看起来简单但特别容易在细节上丢分。下面这些错误新手非常常见把当作字符串内容比较忘记处理空字符串下标访问越界反转时左右指针没有收缩好子串匹配时边界条件写错字符串题的难点往往不在思路本身而在于细节是否严谨。基础操作先把字符串遍历吃透和数组一样字符串题里最常见的第一步也是遍历。1. 从前往后遍历字符串publicstaticvoidprintChars(Strings){for(inti0;is.length();i){System.out.println(s.charAt(i));}}这类写法非常常见适用于统计字符种类判断字符是否合法查找某个字符第一次出现的位置比较相邻字符关系时间复杂度通常是O(n)其中n表示字符串长度。2. 转成字符数组再处理有些题目需要频繁修改字符这时会更适合先转成字符数组。publicstaticvoidprintCharsByArray(Strings){char[]charss.toCharArray();for(charch:chars){System.out.println(ch);}}为什么这样做因为在 Java 中String是不可变的。如果你频繁拼接或修改直接操作String往往不如操作char[]或StringBuilder更合适。第一类高频题字符统计字符统计类问题是字符串入门里最常见的一种。它的核心通常只有一句话遍历字符串并记录每个字符出现了多少次。示例 1统计某个字符出现的次数publicstaticintcountChar(Strings,chartarget){intcount0;for(inti0;is.length();i){if(s.charAt(i)target){count;}}returncount;}例如intanscountChar(banana,a);// 3这类题的关键很简单准备一个计数变量遍历字符串满足条件就累加时间复杂度是O(n)空间复杂度是O(1)示例 2统计每个字符出现的频率如果题目要求统计所有字符出现次数最常见会用哈希表。importjava.util.HashMap;importjava.util.Map;publicstaticMapCharacter,IntegercountFrequency(Strings){MapCharacter,IntegerfreqnewHashMap();for(inti0;is.length();i){charchs.charAt(i);freq.put(ch,freq.getOrDefault(ch,0)1);}returnfreq;}这种题非常经典后面很多字符串题都会建立在“先统计频率”这个动作之上比如判断两个字符串是否为字母异位词找到第一个不重复字符统计出现次数最多的字符示例 3只统计英文字母有些题会要求你忽略数字、空格或标点这时就要先做字符判断。publicstaticintcountLetters(Strings){intcount0;for(inti0;is.length();i){charchs.charAt(i);if(Character.isLetter(ch)){count;}}returncount;}这类题提醒你一件事字符串题经常不只是“遍历”而是“遍历 条件筛选”。第二类高频题字符串反转字符串反转是非常典型的入门题但它背后对应的是非常重要的双指针思想。示例 1使用StringBuilder反转如果只是快速得到反转结果Java 中最直接的写法是publicstaticStringreverseString(Strings){returnnewStringBuilder(s).reverse().toString();}这个写法非常简洁适合工程开发或快速处理。但如果你正在学算法重点不应该只停在“会调用 API”而是要理解如果不用现成方法如何自己实现反转示例 2双指针手写反转publicstaticStringreverseByTwoPointers(Strings){char[]charss.toCharArray();intleft0;intrightchars.length-1;while(leftright){chartempchars[left];chars[left]chars[right];chars[right]temp;left;right--;}returnnewString(chars);}这个过程的本质是左指针从头开始右指针从尾开始两边字符交换指针不断向中间靠拢例如字符串hello交换过程大致是h e l l o o e l l h o l l e h时间复杂度通常是O(n)空间复杂度通常是O(n)因为这里转成了字符数组。反转类题的常见变形后续你会遇到很多反转变形题只反转单词顺序只反转元音字母每k个字符反转一次判断一个字符串是否为回文虽然题目外观不同但核心仍然是双指针 边界处理。第三类高频题字符串匹配所谓字符串匹配最基础的理解就是判断某个字符、某个子串是否出现在另一个字符串中。这是字符串题里极高频的一类。示例 1查找字符第一次出现的位置publicstaticintfirstIndexOfChar(Strings,chartarget){for(inti0;is.length();i){if(s.charAt(i)target){returni;}}return-1;}这本质上就是线性扫描复杂度通常为O(n)。示例 2判断一个字符串是否包含某个子串如果使用 Java 自带方法可以直接这样写publicstaticbooleancontainsSubString(Strings,Stringtarget){returns.contains(target);}但从算法学习角度更重要的是知道最基础的暴力匹配思路。示例 3手写最基础的子串匹配publicstaticintindexOfSubString(Stringtext,Stringpattern){intntext.length();intmpattern.length();for(inti0;in-m;i){intj0;while(jmtext.charAt(ij)pattern.charAt(j)){j;}if(jm){returni;}}return-1;}这个写法的含义是枚举主串中的每一个可能起点从该起点开始逐个字符比较如果全部匹配成功就返回起始位置例如intindexindexOfSubString(algorithm,go);// 2这就是最原始的字符串匹配思想。后面你学到 KMP 时会发现 KMP 本质上也是在解决“匹配时如何少回退”这个问题。一道综合基础题判断回文字符串字符串入门里有一类非常经典的综合题就是回文判断。所谓回文就是正着读和反着读都一样例如levelradarabba示例判断字符串是否为回文publicstaticbooleanisPalindrome(Strings){intleft0;intrights.length()-1;while(leftright){if(s.charAt(left)!s.charAt(right)){returnfalse;}left;right--;}returntrue;}这道题非常重要因为它同时考察了字符串访问双指针移动边界判断提前返回如果你能把这道题真正写熟很多基础字符串题都会轻松很多。字符串题的常见套路先分类再选方法字符串题看起来很多其实初学阶段大致可以先分成下面几类题型常见方法典型关键词字符统计类遍历、计数、哈希表次数、频率、重复反转类双指针、字符数组反转、回文、交换匹配类扫描、比较、定位包含、查找、子串过滤处理类条件判断、跳过无效字符空格、标点、大小写构造类StringBuilder拼接、生成新字符串字符串题不要上来就硬写先判断题型再决定用遍历、双指针、哈希表还是构造。易错点新手做字符串题最容易踩的坑1. 用比较字符串内容在 Java 中比较的是引用地址equals()比较的是字符串内容例如Stringaabc;StringbnewString(abc);System.out.println(a.equals(b));// true如果你要比较内容优先考虑equals()。2. 忘记处理空字符串例如Strings;很多人写代码时默认字符串一定有内容结果一访问charAt(0)就出错。3.charAt(i)越界字符串下标范围是0 ~ s.length() - 1任何访问超出这个范围都会抛异常。4. 反转时忘记移动指针双指针题里如果忘了写left;right--;程序就可能陷入死循环。5. 子串匹配时边界写错例如暴力匹配中外层循环常见写法应该是in-m如果写错就可能漏掉最后一个可能起点或者直接越界。6. 频繁用拼接长字符串在循环中不断使用字符串相加性能通常不理想。如果需要反复构造字符串更推荐使用StringBuilder。publicstaticStringbuildString(intn){StringBuildersbnewStringBuilder();for(inti0;in;i){sb.append(i);}returnsb.toString();}7. 没有先想清楚“题目比较的到底是什么”字符串题里常见的比较对象有字符整个字符串子串忽略大小写后的结果去掉非字母数字后的结果如果不先想清楚后面代码很容易越写越乱。复杂度总结字符串基础操作要有直觉下面这些复杂度建议尽快形成条件反射操作常见时间复杂度说明按下标访问字符O(1)可以直接通过位置读取遍历整个字符串O(n)逐个字符处理统计字符次数O(n)一次扫描即可反转字符串O(n)每个字符最多处理一次暴力子串匹配O(n * m)主串和模式串逐步比较这里的n表示主串长度m表示模式串长度总结字符串入门关键不是 API而是套路意识很多人学字符串时会把注意力放在各种 Java 字符串方法上。这些方法当然重要但如果只停留在“背 API”算法能力很难真正提升。这篇文章你应该清楚的结论字符串本质上也是一种可遍历的数据序列字符统计类问题核心是“遍历 计数”反转类问题核心往往是“双指针”匹配类问题核心是“扫描 比较 边界”很多字符串题的难点不在思路而在细节处理字符串题表面看是在处理文字实际上考的是遍历、比较、边界和套路识别能力。
第03篇：字符串入门
概述为什么字符串是算法题里的高频主角学完数组之后字符串通常就是下一站。原因并不复杂很多题目的输入本质上就是一段文本字符串底层往往和数组处理思路高度相似双指针、哈希表、滑动窗口、KMP 等经典算法很多都和字符串密切相关面试中非常喜欢考察字符串因为它能同时检验遍历能力、边界处理能力和代码细节能力这篇文章的目标不是单纯讲String的语法而是帮助你建立字符串题最基础的 4 种意识字符串本质上也是一种可遍历的数据序列字符统计类问题通常围绕“计数”展开字符串反转类问题通常围绕“双指针”展开字符匹配类问题通常围绕“比较、扫描、定位”展开学完这篇你应该能看懂大多数基础字符串题到底在考什么。核心概念字符串到底是什么字符串可以理解为由多个字符按顺序组成的一段文本数据。例如Stringsalgorithm;这里的s就是一个字符串它由多个字符依次组成a l g o r i t h m如果从算法角度看字符串和数组非常像都可以按位置访问元素都可以从头到尾遍历都经常会用到下标都很依赖边界判断不同点在于字符串处理的对象是字符而不是普通整数。在 Java 中如果你想访问字符串中的某个字符最常见的方式是Stringshello;charchs.charAt(1);// e字符串长度则通过length()获取intns.length();原理字符串题为什么特别考验细节数组题里很多元素比较的是数值大小而字符串题里除了遍历你还会频繁遇到这些问题当前字符是不是字母是否和另一个字符相等大小写是否要统一空格和标点是否需要跳过比较的是字符、子串还是整个字符串所以字符串题经常看起来简单但特别容易在细节上丢分。下面这些错误新手非常常见把当作字符串内容比较忘记处理空字符串下标访问越界反转时左右指针没有收缩好子串匹配时边界条件写错字符串题的难点往往不在思路本身而在于细节是否严谨。基础操作先把字符串遍历吃透和数组一样字符串题里最常见的第一步也是遍历。1. 从前往后遍历字符串publicstaticvoidprintChars(Strings){for(inti0;is.length();i){System.out.println(s.charAt(i));}}这类写法非常常见适用于统计字符种类判断字符是否合法查找某个字符第一次出现的位置比较相邻字符关系时间复杂度通常是O(n)其中n表示字符串长度。2. 转成字符数组再处理有些题目需要频繁修改字符这时会更适合先转成字符数组。publicstaticvoidprintCharsByArray(Strings){char[]charss.toCharArray();for(charch:chars){System.out.println(ch);}}为什么这样做因为在 Java 中String是不可变的。如果你频繁拼接或修改直接操作String往往不如操作char[]或StringBuilder更合适。第一类高频题字符统计字符统计类问题是字符串入门里最常见的一种。它的核心通常只有一句话遍历字符串并记录每个字符出现了多少次。示例 1统计某个字符出现的次数publicstaticintcountChar(Strings,chartarget){intcount0;for(inti0;is.length();i){if(s.charAt(i)target){count;}}returncount;}例如intanscountChar(banana,a);// 3这类题的关键很简单准备一个计数变量遍历字符串满足条件就累加时间复杂度是O(n)空间复杂度是O(1)示例 2统计每个字符出现的频率如果题目要求统计所有字符出现次数最常见会用哈希表。importjava.util.HashMap;importjava.util.Map;publicstaticMapCharacter,IntegercountFrequency(Strings){MapCharacter,IntegerfreqnewHashMap();for(inti0;is.length();i){charchs.charAt(i);freq.put(ch,freq.getOrDefault(ch,0)1);}returnfreq;}这种题非常经典后面很多字符串题都会建立在“先统计频率”这个动作之上比如判断两个字符串是否为字母异位词找到第一个不重复字符统计出现次数最多的字符示例 3只统计英文字母有些题会要求你忽略数字、空格或标点这时就要先做字符判断。publicstaticintcountLetters(Strings){intcount0;for(inti0;is.length();i){charchs.charAt(i);if(Character.isLetter(ch)){count;}}returncount;}这类题提醒你一件事字符串题经常不只是“遍历”而是“遍历 条件筛选”。第二类高频题字符串反转字符串反转是非常典型的入门题但它背后对应的是非常重要的双指针思想。示例 1使用StringBuilder反转如果只是快速得到反转结果Java 中最直接的写法是publicstaticStringreverseString(Strings){returnnewStringBuilder(s).reverse().toString();}这个写法非常简洁适合工程开发或快速处理。但如果你正在学算法重点不应该只停在“会调用 API”而是要理解如果不用现成方法如何自己实现反转示例 2双指针手写反转publicstaticStringreverseByTwoPointers(Strings){char[]charss.toCharArray();intleft0;intrightchars.length-1;while(leftright){chartempchars[left];chars[left]chars[right];chars[right]temp;left;right--;}returnnewString(chars);}这个过程的本质是左指针从头开始右指针从尾开始两边字符交换指针不断向中间靠拢例如字符串hello交换过程大致是h e l l o o e l l h o l l e h时间复杂度通常是O(n)空间复杂度通常是O(n)因为这里转成了字符数组。反转类题的常见变形后续你会遇到很多反转变形题只反转单词顺序只反转元音字母每k个字符反转一次判断一个字符串是否为回文虽然题目外观不同但核心仍然是双指针 边界处理。第三类高频题字符串匹配所谓字符串匹配最基础的理解就是判断某个字符、某个子串是否出现在另一个字符串中。这是字符串题里极高频的一类。示例 1查找字符第一次出现的位置publicstaticintfirstIndexOfChar(Strings,chartarget){for(inti0;is.length();i){if(s.charAt(i)target){returni;}}return-1;}这本质上就是线性扫描复杂度通常为O(n)。示例 2判断一个字符串是否包含某个子串如果使用 Java 自带方法可以直接这样写publicstaticbooleancontainsSubString(Strings,Stringtarget){returns.contains(target);}但从算法学习角度更重要的是知道最基础的暴力匹配思路。示例 3手写最基础的子串匹配publicstaticintindexOfSubString(Stringtext,Stringpattern){intntext.length();intmpattern.length();for(inti0;in-m;i){intj0;while(jmtext.charAt(ij)pattern.charAt(j)){j;}if(jm){returni;}}return-1;}这个写法的含义是枚举主串中的每一个可能起点从该起点开始逐个字符比较如果全部匹配成功就返回起始位置例如intindexindexOfSubString(algorithm,go);// 2这就是最原始的字符串匹配思想。后面你学到 KMP 时会发现 KMP 本质上也是在解决“匹配时如何少回退”这个问题。一道综合基础题判断回文字符串字符串入门里有一类非常经典的综合题就是回文判断。所谓回文就是正着读和反着读都一样例如levelradarabba示例判断字符串是否为回文publicstaticbooleanisPalindrome(Strings){intleft0;intrights.length()-1;while(leftright){if(s.charAt(left)!s.charAt(right)){returnfalse;}left;right--;}returntrue;}这道题非常重要因为它同时考察了字符串访问双指针移动边界判断提前返回如果你能把这道题真正写熟很多基础字符串题都会轻松很多。字符串题的常见套路先分类再选方法字符串题看起来很多其实初学阶段大致可以先分成下面几类题型常见方法典型关键词字符统计类遍历、计数、哈希表次数、频率、重复反转类双指针、字符数组反转、回文、交换匹配类扫描、比较、定位包含、查找、子串过滤处理类条件判断、跳过无效字符空格、标点、大小写构造类StringBuilder拼接、生成新字符串字符串题不要上来就硬写先判断题型再决定用遍历、双指针、哈希表还是构造。易错点新手做字符串题最容易踩的坑1. 用比较字符串内容在 Java 中比较的是引用地址equals()比较的是字符串内容例如Stringaabc;StringbnewString(abc);System.out.println(a.equals(b));// true如果你要比较内容优先考虑equals()。2. 忘记处理空字符串例如Strings;很多人写代码时默认字符串一定有内容结果一访问charAt(0)就出错。3.charAt(i)越界字符串下标范围是0 ~ s.length() - 1任何访问超出这个范围都会抛异常。4. 反转时忘记移动指针双指针题里如果忘了写left;right--;程序就可能陷入死循环。5. 子串匹配时边界写错例如暴力匹配中外层循环常见写法应该是in-m如果写错就可能漏掉最后一个可能起点或者直接越界。6. 频繁用拼接长字符串在循环中不断使用字符串相加性能通常不理想。如果需要反复构造字符串更推荐使用StringBuilder。publicstaticStringbuildString(intn){StringBuildersbnewStringBuilder();for(inti0;in;i){sb.append(i);}returnsb.toString();}7. 没有先想清楚“题目比较的到底是什么”字符串题里常见的比较对象有字符整个字符串子串忽略大小写后的结果去掉非字母数字后的结果如果不先想清楚后面代码很容易越写越乱。复杂度总结字符串基础操作要有直觉下面这些复杂度建议尽快形成条件反射操作常见时间复杂度说明按下标访问字符O(1)可以直接通过位置读取遍历整个字符串O(n)逐个字符处理统计字符次数O(n)一次扫描即可反转字符串O(n)每个字符最多处理一次暴力子串匹配O(n * m)主串和模式串逐步比较这里的n表示主串长度m表示模式串长度总结字符串入门关键不是 API而是套路意识很多人学字符串时会把注意力放在各种 Java 字符串方法上。这些方法当然重要但如果只停留在“背 API”算法能力很难真正提升。这篇文章你应该清楚的结论字符串本质上也是一种可遍历的数据序列字符统计类问题核心是“遍历 计数”反转类问题核心往往是“双指针”匹配类问题核心是“扫描 比较 边界”很多字符串题的难点不在思路而在细节处理字符串题表面看是在处理文字实际上考的是遍历、比较、边界和套路识别能力。
