字符串用法总结基础入门

字符串是数据结构与算法中最基础、考察频率最高的模块无论是校招笔试、蓝桥杯等竞赛还是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(lr){ char ts[l];s[l]s[r];s[r]t; l;r--; } } char* reverseWords(char* s){ int nstrlen(s); int i0; while(in){ int ji; // 找到单词末尾 while(jns[j]! ) j; reverse(s,i,j-1); ij1; } 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(strsSize0) return ; int idx0; while(1){ char cstrs[0][idx]; // 逐个字符串比对 for(int i0;istrsSize;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(l0rstrlen(s)s[l]s[r]){l--;r;} return r-l-1; } char* longestPalindrome(char* s) { int nstrlen(s); if(n0) return ; int start0,end0; for(int i0;in;i){ int aexpand(s,i,i); //奇数 int bexpand(s,i,i1); //偶数 int maxlenab?a:b; if(maxlenend-start){ starti-(maxlen-1)/2; endimaxlen/2; } } //手动截断补结束符 static char res[1005]; int p0; for(int istart;iend;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 left0,maxlen0,nstrlen(s); for(int right0;rightn;right){ if(hash[s[right]]){ //更新左边界 lefthash[s[right]]left?hash[s[right]]:left; } hash[s[right]]right1; int nowright-left1; maxlennowmaxlen?now:maxlen; } return maxlen; }易错点提示1.右指针只右移不重置是线性时间核心。2.窗口长度计算严格核对下标差值避免加减1下标错误。3.哈希数组做题前全局清零防止多组测试用例残留脏数据。三、字符串模式匹配算法子串查找核心1KMP算法算法定义预处理模式串生成 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 j0,lenstrlen(p); next[0]0; for(int i1;ilen;i){ while(j0p[i]!p[j]) jnext[j-1]; if(p[i]p[j]) j; next[i]j; } } //KMP匹配主逻辑 int kmp(char *s,char *p){ int nstrlen(s),mstrlen(p); if(m0) return 0; int next[100005]; getNext(p,next); int j0; for(int i0;in;i){ while(j0s[i]!p[j]) jnext[j-1]; if(s[i]p[j]) j; if(jm) return i-m1; } return -1; }易错点提示1.C语言数组下标从0开始回退公式严格写 j next[j-1] 。2.主串指针全程不回退是KMP灵魂千万别写成BF式双回退。3.next数组开辟和模式串等长整型数组栈空间不够就全局定义防栈溢出。