当前位置：首页 > news >正文

【优选算法 | 字符串】字符串模拟题精选：思维+实现解析

news 来源：原创 2025/7/4 18:46:44

在这里插入图片描述

算法	相关知识点	可以通过点击	以下链接进行学习	一起加油！
双指针	滑动窗口	二分查找	前缀和	位运算
模拟	链表	哈希表

在众多字符串算法题中，有一类题目看起来没有太多算法技巧，却经常让人“翻车”——那就是字符串模拟题。这类题型往往不依赖复杂的数据结构或高级算法，更多的是对逻辑构造能力、字符串操作细节以及边界处理的考察。本文将通过几个典型字符串模拟题的拆解，帮助你梳理解题思路、掌握通用技巧，从而在这类题目中稳住基本盘。

请添加图片描述

Alt

🌈个人主页：是店小二呀
🌈C/C++专栏：C语言\ C++
🌈初/高阶数据结构专栏：初阶数据结构\ 高阶数据结构
🌈Linux专栏： Linux
🌈算法专栏：算法
🌈Mysql专栏:Mysql

🌈你可知:无人扶我青云志我自踏雪至山巅请添加图片描述

文章目录

- 14. 最长公共前缀
- 5. 最长回文子串
- 67. 二进制求和
- 43. 字符串相乘

14. 最长公共前缀

【题目】：14. 最长公共前缀
在这里插入图片描述

【算法思路】

解法一：两两比较

在这里插入图片描述

通过两两比较的方式，不断循环寻找字符不相等的位置，利用 substr 接口进行字符串剪切。这里，‘最长公共前缀’的意思是根据木桶效应，取最短字符串的长度作为‘最长公共前缀’的上限。

【代码实现】

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {//解法一：两两结合string tmp = strs[0];for(int i = 1; i< strs.size(); i++)tmp = findpRrefix(tmp, strs[i]);return tmp;}string findpRrefix(string& s1, string& s2){int i = 0;while(i < min(s1.size(), s2.size()) && s1[i] == s2[i]) i++;return s1.substr(0, i);}
};

解法二：统一比较

在这里插入图片描述

使用 char 类型变量记录字符串中的元素，通过循环逐个比较字符是否相等。考虑到‘最长公共前缀’的上限，当某段完全相同的字符串长度等于当前遍历的字符串长度时，说明已经达到了公共前缀的上限，此时可以直接返回结果。

【代码实现】

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {//解法二：统计比较for(int j = 0; j < strs[0].size(); j++){char ch = strs[0][j];for(int i = 0; i < strs.size(); i++){if( j == strs[i].size()  || strs[i][j] != ch) return strs[0].substr(0,j);}}return strs[0];}
};

5. 最长回文子串

【题目】：5. 最长回文子串

在这里插入图片描述

【算法思路】

解法：中心扩展算法

固定一个中心点。
从中心开始，向两边扩展。

注意：需要同时考虑奇数长度和偶数长度的回文情况。扩展过程中，若遇到越界或不符合回文性质时，停止并返回。中心扩展算法特别适用于回文数的对称特性。

【代码实现】

class Solution {
public:string longestPalindrome(string s) {//中心扩展算法int begin = 0, len = 0;int n = s.size();for(int i = 0; i < n; i++) //依次枚举所有的中点{int left = i, rigth = i;//奇数扩张while(left >= 0 && rigth < n && s[left] == s[rigth]){left--;rigth++;}if(rigth - left - 1 > len){begin = left + 1;len = rigth - left - 1;}//偶数扩张left = i, rigth = i + 1;while(left >= 0 && rigth < n && s[left] == s[rigth]){left--;rigth++;}if(rigth - left - 1 > len){begin = left + 1;len = rigth - left - 1;}}return s.substr(begin,len);}
};

67. 二进制求和

【题目】：67. 二进制求和

在这里插入图片描述

【算法思路】

解法：高精度模拟加减乘除

高精度算法模拟了列竖式计算过程，通常称为‘二进制高精度加法算法’，对于两个字符串的处理从低位开始。需要特别注意进位处理逻辑，并且要处理前导零的情况。判断条件为：当 cur >= 0 时，继续处理到最前的数据，若不需要加上原数据，默认加0。

数字字符转换为整型时：数字字符 - '0' 即得到整型值。

最后，使用 reverse 进行翻转，以符合题目的要求。

在这里插入图片描述

【代码实现】

class Solution {
public:string addBinary(string a, string b) {int cur1 = a.size() - 1, cur2 = b.size() - 1;int t = 0;string ret;while(cur1 >= 0 || cur2 >=0 || t ){if(cur1 >= 0)  t += a[cur1--] - '0'; if(cur2 >= 0)  t += b[cur2--] - '0'; ret += t % 2 + '0';t /= 2;}reverse(ret.begin(), ret.end());return ret;}
};

43. 字符串相乘

【题目】：43. 字符串相乘

在这里插入图片描述

【算法思路】

解法一："模拟"小学的列竖式运算
在这里插入图片描述

解法二：无进位相乘然后相加，最后处理进位

在这里插入图片描述

关于此类高精度题目，推荐先将原始字符串进行反转，因为列竖式计算是从低位开始的。对于两个字符串，先反转它们，再将数字字符转换为整型，通过数组存储结果。我们创建的数组大小为 m + n - 1，其中 m 和 n 分别是两个字符串的长度。通过数学或绘图分析，可以发现这个刚好满足累加所需的存储空间。

这里使用无进位相乘然后相加，最后再处理进位。由于无论是先进行进位还是后进行进位，最终的结果是相同的，因此我们推荐先将结果存储下来，然后再进行进位处理，这样更为方便和简洁，避免了细节很多存在的问题。

算法步骤：

第一步:将输入的两个字符串反转，以便从低位开始进行处理。

第二步：对于两个字符串中的数字，通过下标相加，其两个数字结果正好对应数组中相应位置的值。在进行加法时，需使用 += 来累加结果。

第三步：在处理完所有操作后，可能会出现前导零的情况。最终需要使用 reverse 进行翻转，并去掉多余的前导零。可以通过以下代码来去除前导零：while (ret.size() > 1 && ret.back() == '0') ret.pop_back();

【代码实现】

class Solution 
{
public:string multiply(string nums1, string nums2) {int n = nums1.size(), m = nums2.size();//字符串反转reverse(nums1.begin(), nums1.end());reverse(nums2.begin(), nums2.end());vector<int> nums(m + n - 1);for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)nums[i + j] += ((nums1[i] - '0') * (nums2[j] - '0')) ;//进位处理string ret;int t = 0, cur = 0;while( cur < m + n -1 || t){if(cur < m + n -1) t += nums[cur++];ret += t % 10 + '0';t /= 10;}//4.处理前导零while(ret.size() > 1 && ret.back() == '0') ret.pop_back();reverse(ret.begin(), ret.end());return ret;}
};

在这里插入图片描述
快和小二一起踏上精彩的算法之旅！关注我，我们将一起破解算法奥秘，探索更多实用且有趣的知识，开启属于你的编程冒险！

文章目录

14. 最长公共前缀

5. 最长回文子串

67. 二进制求和

43. 字符串相乘

相关文章：