字符串用法总结基础入门

字符串是数据结构与算法中最基础、考察频率最高的模块，无论是校招笔试、蓝桥杯等竞赛，还是LeetCode刷题，子串查找、匹配、最优解等相关题型始终是核心考点。

一、字符串基础操作算法

（1）字符串反转

将字符串的字符顺序完全颠倒，如输入 hello ，输出 olleh ，是字符串最基础的操作，也是复杂字符串算法的基础。

核心原理：

1. 采用原地双指针法，无需额外开辟数组空间，节省内存开销。
2. 定义左指针 left 指向字符串起始下标（索引0），右指针 right 指向字符串末尾下标（索引 len-1 ）
3. 交换左右指针指向的字符，完成后左指针向右移动一位，右指针向左移动一位。
4. 当 left >= right 时，说明所有字符交换完成，循环终止。

算法复杂度：

- 时间复杂度：O(n)，n为字符串长度，只需遍历一半字符即可完成交换；
- 空间复杂度：O(1)，原地操作，仅使用常数级临时变量。

LeetCode真题：344. 反转字符串

题目精细化描述：

编写一个函数，其作用是将输入的字符数组反转过来，必须在原数组上操作，使用O(1)的额外空间。

逐行代码实现：

#include <stdio.h> #include <string.h> // 原地反转字符数组 void reverseString(char* s, int sSize) { int left = 0; int right = sSize - 1; while (left < right) { // 交换 char temp = s[left]; s[left] = s[right]; s[right] = temp; left++; right--; } }

易错点提示：

1. C语言字符串依赖 \0 结尾，计算长度必须用 strlen() ，不可手动数下标忽略结束符。

2. 循环终止条件严格写 left < right ，写 <= 会导致中间奇数位字符重复交换，无意义且浪费性能。

3. 函数传参若为 const char* 只读指针，无法原地修改，必须传入可读写字符数组 char[] 。

（2）字符串大小写转换

将字符串中的大写字母转为小写、小写转大写，或统一转为小写/大写，纯基于ASCII码值差值运算实现。

核心原理：

1. 大写字母 A-Z 的ASCII码值范围：65-90，小写字母 a-z 的ASCII码值范围：97-122。

2. 大小写字母ASCII码差值固定为32：大写转小写 +32 ，小写转大写 -32 。

3. 遍历字符数组每一个字符，判断范围后执行运算，非字母字符直接跳过。

算法复杂度：

1.时间复杂度：O(n)，n为字符串长度，需遍历所有字符。

2.空间复杂度：O(1)，C语言字符数组可原地修改，无需额外开辟空间（区别于Java不可变String）。

LeetCode真题：709. 转换成小写字母

题目精细化描述：

给你一个字符串 s ，将该字符串中的大写字母转换成相同的小写字母，原地修改后返回。

逐行代码实现：

char* toLowerCase(char* s){ int len = strlen(s); for(int i = 0; i < len; i++){ // 判断是否为大写字母区间 if(s[i] >= 'A' && s[i] <= 'Z'){ s[i] += 32; } } return s; }

易错点提示：

1.蓝桥杯考场禁止调用库函数 tolower() ，必须手写ASCII判断+运算，避免判分兼容问题。

2.不要对数字、空格、符号做运算，先区间判断再转换，防止乱码。

3.操作指针字符串时保证内存可写，常量字符串 char* s = "ABC" 只读，修改会段错误。

（3）字符串分割与拼接

算法定义：

按照指定分隔符将字符数组拆分为多个子串，或把多个子串合并为一个完整字符串；C无Java原生 split() / StringBuilder ，需手动遍历实现，竞赛手写核心逻辑。

核心原理：

1. 分割：双指针遍历字符数组，遇到分隔符 ' ' / . 等截断，记录子串起始下标与长度。

2. 拼接：预先计算总长度，开辟足够大小字符数组，循环拷贝子串+分隔符，避免内存溢出。

3. 处理连续空格、首尾空字符，手动过滤无效子串。

算法复杂度：

1.时间复杂度：O(n)，n为字符串总长度，分割和拼接均只需一次遍历。

2.空间复杂度：O(n)，需临时存储分割后的子串缓冲区。

LeetCode真题：557. 反转字符串中的单词 III

题目精细化描述：

给定一个字符串 s ，翻转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

逐行代码实现：

#include <string.h> // 子函数：反转区间[l,r]字符 void reverse(char *s, int l, int r){ while(l<r){ char t=s[l];s[l]=s[r];s[r]=t; l++;r--; } } char* reverseWords(char* s){ int n=strlen(s); int i=0; while(i<n){ int j=i; // 找到单词末尾 while(j<n&&s[j]!=' ') j++; reverse(s,i,j-1); i=j+1; } return s; }

易错点提示：

1.连续空格会产生空缓冲区，必须加判断跳过，防止拷贝乱码。

2.拼接结束手动补 \0 ，C字符串无结束符会内存越界、打印异常。

3.动态拼接优先预分配内存，杜绝边拼边扩容，算法考场防超时。

二、子串基础操作算法

（1）最长公共前缀

算法定义：

给定C语言字符串数组 char strs[][] ，查找所有字符串共有的最长前缀子串，无公共前缀返回空串 "" 。

核心原理：

1. 横向扫描法：以第一个字符串作为初始公共前缀基准。

2. 依次遍历剩余字符串，逐字符对比基准与当前串。

3. 字符不匹配则基准末尾截断下标，重新校验。

4. 基准长度归0直接终止，提前剪枝优化效率。

算法复杂度：

1.时间复杂度：O(mn)，m为字符串平均长度，n为字符串数组个数。

2.空间复杂度：O(1)，仅用下标变量遍历，原地比对。

LeetCode真题：14. 最长公共前缀

题目精细化描述：

编写C语言函数，查找小写字母构成的字符串数组的最长公共前缀。

逐行代码实现：

#include <string.h> char* longestCommonPrefix(char** strs, int strsSize) { if(strsSize==0) return ""; int idx=0; while(1){ char c=strs[0][idx]; // 逐个字符串比对 for(int i=0;i<strsSize;i++){ if(!strs[i][idx]||strs[i][idx]!=c){ strs[0][idx]='\0'; return strs[0]; } } idx++; } }

易错点提示：

1.数组空指针、首个字符串为空直接返回 "" ，边界优先判断防崩溃；

2.比对时严格控制下标不超过两个字符串各自 strlen 长度，杜绝数组越界访问。

（2）最长回文子串（中心扩散法）

算法定义：

给定字符数组，找出其中最长的回文子串（正读反读完全相同），C竞赛必考双指针应用题。

核心原理：

1. 回文分两类：奇数长度（单个字符为中心）、偶数长度（相邻两字符为中心）；

2. 遍历每个下标，分别启动两种中心向左右同步扩散；

3. 扩散条件：左右下标不越界 && 两端字符相等；

4. 实时更新最长回文的起始下标、记录长度，最后拷贝输出结果。

算法复杂度：

1.时间复杂度：O(n²)，n为字符串长度。

2.空间复杂度：O(1)，纯下标遍历，无额外数组开销。

LeetCode真题：5. 最长回文子串

逐行代码展示：

#include <string.h> // 扩散函数，返回长度 int expand(char *s,int l,int r){ while(l>=0&&r<strlen(s)&&s[l]==s[r]){l--;r++;} return r-l-1; } char* longestPalindrome(char* s) { int n=strlen(s); if(n==0) return ""; int start=0,end=0; for(int i=0;i<n;i++){ int a=expand(s,i,i); //奇数 int b=expand(s,i,i+1); //偶数 int maxlen=a>b?a:b; if(maxlen>end-start){ start=i-(maxlen-1)/2; end=i+maxlen/2; } } //手动截断补结束符 static char res[1005]; int p=0; for(int i=start;i<=end;i++) res[p++]=s[i]; res[p]='\0'; return res; }

易错点提示：

1.必须同时奇偶双中心扩散，漏一种直接丢测试用例。

2.扩散退出时左右指针已越界，计算合法长度要做下标修正。

3.结果存储手动开辟缓冲区，结尾补 \0 保证字符串合法。

（3）无重复字符的最长子串

算法定义：

找出字符数组中不含重复字符的最长子串长度，C语言滑动窗口+数组哈希映射经典题。

核心原理：

1. 用 int hash[128] 映射ASCII所有字符，记录字符最近出现下标，代替集合，速度更快适配C考场。

2. 双指针滑动窗口：右指针扩张，左指针动态收缩去重。

3. 出现重复字符时更新左边界，同步刷新哈希下标。

4. 全程更新窗口最大长度。

LeetCode真题：3. 无重复字符的最长子串

逐行代码展示：

int lengthOfLongestSubstring(char* s) { int hash[128]={0}; int left=0,maxlen=0,n=strlen(s); for(int right=0;right<n;right++){ if(hash[s[right]]){ //更新左边界 left=hash[s[right]]>left?hash[s[right]]:left; } hash[s[right]]=right+1; int now=right-left+1; maxlen=now>maxlen?now:maxlen; } return maxlen; }

易错点提示：

1.右指针只右移不重置，是线性时间核心。

2.窗口长度计算严格核对下标差值，避免加减1下标错误。

3.哈希数组做题前全局清零，防止多组测试用例残留脏数据。

三、字符串模式匹配算法（子串查找核心）

（1）KMP算法

算法定义：

预处理模式串生成 next 前缀数组，主串指针不回退，彻底解决BF重复比对低效问题。

核心原理：

1. next数组： next[j] 存模式串前j个子串最长相等前后缀长度；

2. 构建next：双指针前后缀推导，不等时j递归回退 next[j-1] ；

3. 匹配逻辑：字符相等i、j同步后移；不等仅j按next回退，主串i不动。

LeetCode真题：28. 找出字符串中第一个匹配项的下标

逐行代码展示：

#include <string.h> //构建next数组 void getNext(char *p,int next[]){ int j=0,len=strlen(p); next[0]=0; for(int i=1;i<len;i++){ while(j>0&&p[i]!=p[j]) j=next[j-1]; if(p[i]==p[j]) j++; next[i]=j; } } //KMP匹配主逻辑 int kmp(char *s,char *p){ int n=strlen(s),m=strlen(p); if(m==0) return 0; int next[100005]; getNext(p,next); int j=0; for(int i=0;i<n;i++){ while(j>0&&s[i]!=p[j]) j=next[j-1]; if(s[i]==p[j]) j++; if(j==m) return i-m+1; } return -1; }

易错点提示：

1.C语言数组下标从0开始，回退公式严格写 j = next[j-1] 。

2.主串指针全程不回退是KMP灵魂，千万别写成BF式双回退。

3.next数组开辟和模式串等长整型数组，栈空间不够就全局定义防栈溢出。