胡凡算法入门篇精选题解（三）：字符串处理与校验的核心模板精讲

如果对胡凡算法内容有兴趣的，可以看看入门篇的前两篇博客：胡凡算法入门篇精选题解（一）：从单调序列到图形输出的综合实践、胡凡算法入门篇精选题解（二）：日期与进制转换的核心技巧精讲

1.回文字符串

核心思路：从头和尾开始遍历，比较各个元素

1.1 何为回文字符串

正着读和反着读都一样的字符串，就是回文字符串

• abcba -> 回文
• level - >回文
• hello ->不是回文

1.2 思路分析

判断一个字符串是否为回文，最常用的方法是对称比较法：

• 首先：获取字符串长度
• 比较对称位置的字符：
  • 第一个字符 vs 最后一个字符
  • 第二个字符 vs 倒数第二个字符
  • 以此类推
• 发现任何不相等的情况，立即返回false
• 所有对称字符都相等，返回true

1.3 代码实现

#include<stdio.h>#include<string.h>//提供我strlen函数#include<stdbool.h>//提供bool类型// 判断是否回文boolisPalindrome(constchar*str){intlen=strlen(str);// 获取字符串长度//len / 2 - 只需比较到字符串中间位置for(inti=0;i<len/2;i++){// 遍历前半段if(str[i]!=str[len-i-1]){// 与对称位置字符不同returnfalse;// 则不是回文}}returntrue;// 前半段与后半段一致时为回文}intmain(){charstr[1000];scanf("%s",str);// 读取输入字符串printf(isPalindrome(str)?"YES":"NO");// 输出判断结果return0;}

当然，也有很多其他的方法，例如：双指针法

boolisPalindrome2(constchar*str){intleft=0;intright=strlen(str)-1;while(left<right){if(str[left]!=str[right]){returnfalse;}left++;right--;}returntrue;}

1.4 可能的错误和注意事项

①忘记处理字符串结束符

// 错误示例charstr[50];scanf("%s",str);// 如果输入长度=50，会溢出//正确做法charstr[51];// 为结束符'\0'预留空间

②整数除法

// 对于长度为5的字符串：len/2 = 2// 比较索引：0↔4, 1↔3（中间字符不需要比较）

③使用const保护数据

boolisPalindrome(constchar*str)// const防止意外修改

2. 单词倒序

2.1何为单词倒序II

这里的单词倒序，是每个单词内部逆序后输出，而保持单词之间的顺序不变，我们要注意单词倒序，和单词内部逆序的概念。

• 单词倒序：单词的顺序反转，但单词内部顺序不变
• 单词内部逆序：每个单词的字母顺序反转，但单词顺序不变

输入:"Hello","World"输出1："World""Hello"-单词倒序 输出:"olleH""dlroW"-单词内部逆序

2.2思路分析

• 首先：读取输入 - 单词有空格，需要读取多个单词（char a[n][m])
• 其次：分割单词 - 讲输入的字符串按空格分割成独立的单词（又或者之间以字符串的方式进行读入）
• 最后：逆序处
  • 1.每个单词内部进行字符逆序，然后输出
  • 2.不用特定逆序，直接倒着打印

2.3 代码实现

①逆序处理：

#include<stdio.h>#include<string.h>#defineMAX_WORDS100// 最大单词数#defineMAX_WORD_LEN11// 最大单词长度（10字符+'\0'）intmain(){charwords[MAX_WORDS][MAX_WORD_LEN];// 存储单词intword_count=0;// 单词计数charword[MAX_WORD_LEN];// 临时存储当前单词charch;intidx=0;// 当前单词字符索引printf("请输入英文单词（用空格分隔）：\n");// 方法1：使用scanf按空格自动分割（最简单）while(scanf("%10s",word)!=EOF){// %10s限制读取10个字符if(word_count<MAX_WORDS){// 逆序当前单词intlen=strlen(word);for(inti=0;i<len/2;i++){chartemp=word[i];word[i]=word[len-1-i];word[len-1-i]=temp;}strcpy(words[word_count++],word);}}// 输出结果printf("处理结果：\n");for(inti=0;i<word_count;i++){printf("%s",words[i]);if(i<word_count-1){printf(" ");}}printf("\n");return0;}

②倒着打印

#include<stdio.h>#include<string.h>#defineMAXN500// 最大单词数量#defineMAXL11// 每个单词最大长度+1charstr[MAXN][MAXL];// 存储输入单词的数组intnum=0;// 实际读取的单词数量intmain(){while(scanf("%s",str[num])!=EOF){// 读取一个单词直到文件结束num++;// 单词计数加一}for(inti=0;i<num;i++){// 顺序遍历每个单词intlen=(int)strlen(str[i]);// 计算当前单词长度for(intj=len-1;j>=0;j--){// 从末尾开始逆序遍历字符printf("%c",str[i][j]);// 输出当前字符}if(i<num-1){// 如果不是最后一个单词printf(" ");// 输出空格分隔}}

2.4 可能的错误和注意事项

①缓冲区溢出：

// 危险代码charword[11];scanf("%s",word);// 如果输入超过10字符，会溢出！// 正确代码scanf("%10s",word);// 限制读取长度

②忘掉字符串结束符

// 错误charword[11];for(inti=0;i<10;i++){word[i]='a'+i;// 没有'\0'，不是有效字符串}// 正确word[10]='\0';// 显式添加结束符

③数组越界：

for(inti=0;i<=len;i++){// 错误：应该是 i < len/2// ...}

④输入限制：

• 题目说每个单词不超过10个字符，但是要考虑’\0’,数组大小应该为11
• 总长度不超过1000，但是要考虑最坏的情况：100个10字符单词

⑤边界处理：

// 处理只有一个单词的情况if(word_count==1){// 不需要控制空格}// 处理空输入（理论上不存在）if(word_count==0){printf("\n");// 只输出换行}

3. 求字符串的公共前缀

3.1 问题理解

公共前缀是指所有字符串都有的、从第一个字符开始的相同部分。例如：

• 输入：[“acting”,“actfps”,“actareg”]
• 公共前缀：”act"
• 因为这三个字符都以“act”开头

3.2 思路分析

• 首先，找到最短的字符串长度（因为公共前缀不可能超过最短字符串的长度）
• 逐字符比较所有字符串
  • 比较所有字符串的第一个字符
  • 比较所有字符串的第二个字符
  • 以此类推…
• 发现不一致时停止
• 输出一致的部分

3.3 代码实现

#include<stdio.h>#include<string.h>#include<stdbool.h>#defineMAXN20// 最大字符串数量#defineMAXL51// 最大字符串长度+1（包含结束符）charstr[MAXN][MAXL];// 存储所有字符串的二维数组intmain(){intn,minL=MAXL;// n: 字符串数量，minL: 最短字符串长度// 1. 读取字符串数量scanf("%d",&n);getchar();// 消耗输入缓冲区中的换行符// 2. 读取所有字符串并找到最短长度for(inti=0;i<n;i++){fgets(str[i],MAXL,stdin);// 读取字符串str[i][strcspn(str[i],"\n")]='\0';// 去除末尾换行符intlen=strlen(str[i]);// 计算当前字符串长度if(len<minL){minL=len;// 更新最短长度}}// 3. 逐字符比较所有字符串for(intj=0;j<minL;j++){// j: 字符位置索引bool isSame=true;// 标记当前位置字符是否相同// 比较所有字符串在第j个位置的字符for(inti=1;i<n;i++){// i: 字符串索引（从1开始）if(str[i][j]!=str[0][j]){// 与第一个字符串比较isSame=false;// 发现不同字符break;// 跳出内层循环}}if(isSame){putchar(str[0][j]);// 所有字符串该位置字符相同，输出}else{break;// 发现不同字符，停止比较}}putchar('\n');// 输出换行符return0;}

3.4 可能的错误和注意事项

①忘记处理换行符

// 错误scanf("%s",str[i]);// 不能处理带空格的输入// 正确fgets(str[i],MAXL,stdin);str[i][strcspn(str[i],"\n")]='\0';

• 如果你用了scanf，遇到字符串时，记得加getchar()（读取换行符）
• 如果采用fgets，他会默认遇到\n结束，但是会直接在\n加\0(“hello”

charbuffer[100];fgets(buffer,sizeof(buffer),stdin);//输入“hello” -> "hello\n\0"str[i][strcspn(str[i],"\n")]='\0'//strcspn(str1,str2) - 扫描str1中首次出现的str2中的任何字符，返回在这个字符在str1的下标//这里的用途就是在str[i]中找到'\n'的位置//例如这个\n在上述位置是5 - 所以返回5

②数组越界

// 错误：假设所有字符串长度相同for(intj=0;j<strlen(str[0]);j++)// 如果str[0]不是最短的...// 正确：先找到最短长度intminL=MAXL;for(inti=0;i<n;i++){intlen=strlen(str[i]);if(len<minL)minL=len;}

4.连续相同字符统计

4.1 问题理解

统计字符串中连续出现的相同字符的个数，并按顺序输出每个字符及其连续出现的次数。例如：

输入："aaabbbcccaa"输出： a3b3c3a2

4.2 核心算法思路

双指针滑动窗口的思路：

• 首先：外层循环遍历字符串的每个字符段
• 其次：内层循环统计当前字符连续出现的次数
• 然后：输出当前字符及其出现次数
• 移动到下一个不同的字符段

4.3 代码实现

#include<stdio.h>#include<string.h>#defineMAXL101charstr[MAXL];intmain(){// 读取输入字符串scanf("%s",str);intidx=0;// 当前扫描位置下标intlen=strlen(str);// 字符串总长度// 从左到右遍历整个字符串while(idx<len){// 输出当前字符printf("%c ",str[idx++]);intcnt=1;// 统计本字符的出现次数，初始为1// 只要下一个字符和当前字符相同，就继续累加计数while(idx<len&&str[idx]==str[idx-1]){cnt++;idx++;}// 打印这一段连续字符的总次数printf("%d\n",cnt);}return0;}

当然，C++这种表示也很容易看懂

#include<iostream>#include<vector>#include<string>using namespace std;intmain(){string str;cin>>str;intlength=str.size();for(inti=0;i<length;i++){intcount=1;// 当前字符至少出现1次// 统计连续相同字符的数量for(intj=i+1;j<length;j++){if(str[i]==str[j]){count++;}else{break;}}printf("%c %d\n",str[i],count);// 跳过已经统计过的连续字符i+=count-1;}return0;}

4.4 可能的错误和注意事项

①空字符串：

// 根据题目描述，输入是非空字符串// 但代码应该有一定的健壮性if(len==0){return0;// 空字符串，直接返回}

②超长字符串：

// 题目限制长度不超过100// 但可以添加保护if(len>=MAXL-1){printf("输入字符串过长\n");return1;}

5.C语言合法变量名

• 这里直接用字符串来做检查就可以了：

#include<iostream>#include<string>using namespace std;intmain(){string str;cin>>str;// 读取输入字符串bool result=true;// 合法性标志，初始为 trueintlen=str.size();// 计算字符串长度// 判断首字符是否为字母或下划线if(!((str[0]>='A'&&str[0]<='Z')||(str[0]>='a'&&str[0]<='z')||str[0]=='_')){result=false;// 首字符非法，标记为 false}// 检查剩余字符是否均为字母、数字或下划线for(inti=1;i<len;i++){if(!((str[i]>='A'&&str[i]<='Z')||(str[i]>='a'&&str[i]<='z')||(str[i]>='0'&&str[i]<='9')||str[i]=='_')){result=false;// 出现非法字符，标记为 falsebreak;// 提前退出循环}}cout<<(result?"YES":"NO");// 输出结果return0;}