字符串算法篇——字里乾坤，算法织梦，解构字符串的艺术（下）
文章目录
前言
上篇我们介绍了常用的字符串及其相关原理应用，本篇将结合具体题目，进一步深化对于字符串算法的掌握运用。
第一章：最长公共前缀
1.1 题目链接：https://leetcode.cn/problems/longest-common-prefix/description/
1.2 题目分析：
- 现给出字符串数组，要求返回所有字符串的最长公共前缀
1.3 思路讲解：
解法⼀（两两⽐较)：
我们可以先找出前两个的最⻓公共前缀，然后拿这个最⻓公共前缀依次与后⾯的字符串⽐较，这样就可以找出所有字符串的最⻓公共前缀。\
解法⼆（统⼀⽐较）：
题⽬要求多个字符串的公共前缀，我们可以逐位⽐较这些字符串，哪⼀位出现了不同，就在哪⼀位截⽌。
1.4 代码实现：
两两比较代码示例：
classSolution{public: string longestCommonPrefix(vector<string>& strs){// 解法⼀：两两⽐较 string ret = strs[0];for(int i =1; i < strs.size(); i++) ret =findCommon(ret, strs[i]);return ret;} string findCommon(string& s1, string& s2){int i =0;while(i <min(s1.size(), s2.size())&& s1[i]== s2[i]) i++;return s1.substr(0, i);}};统一比较代码示例：
classSolution{public: string longestCommonPrefix(vector<string>& strs){//所有字符串一起 逐个比较 string ret=strs[0];for(int i=0;i<ret.size();i++){char temp=strs[0][i];for(int j=1;j<strs.size();j++){if(i==strs[j].size()||temp!=strs[j][i]){return ret.substr(0,i);}}}return ret;}};第二章：最长回文子串
2.1 题目链接：https://leetcode.cn/problems/longest-palindromic-substring/description/
2.2 题目分析：
题目要求找出字符串s中的最长回文子串，我们先来回顾一下什么是回文串。
回文串：即正反形式相同的字符串，例如aba
2.3 思路讲解：
本题我们可以采用中心拓展算法
- 对于⼀个⼦串⽽⾔，如果它是回⽂串，并且⻓度⼤于 2，那么将它⾸尾的两个字⺟去除之后，它仍然是个回⽂串。如此这样去除，⼀直除到⻓度⼩于等于 2 时呢？⻓度为 1 的，⾃⾝与⾃⾝就构成回⽂；⽽⻓度为 2 的，就要判断这两个字符是否相等了。
- 从这个性质可以反推出来，从回⽂串的中⼼开始，往左读和往右读也是⼀样的。那么，是否可以枚举回⽂串的中⼼呢？
- 从中⼼向两边扩展，如果两边的字⺟相同，我们就可以继续扩展；如果不同，我们就停⽌扩展。
- 这样只需要⼀层 for 循环，我们就可以完成先前两层 for 循环的⼯作量。
2.4 代码实现：
classSolution{public: string longestPalindrome(string s){int n=s.size();int left=0,right=0,len=0,begin=0;for(int i=0;i<n;i++){//奇数次拓展 left=i,right=i;while(left>=0&&right<n&&s[left]==s[right]){ left--; right++;}if(right-left-1>len){ begin=left+1; len=right-left-1;}//偶数次拓展 left=i,right=i+1;while(left>=0&right<n&&s[left]==s[right]){ left--; right++;}if(right-left-1>len){ begin=left+1; len=right-left-1;}}return s.substr(begin,len);}};第三章：二进制求和
3.1 题目链接：https://leetcode.cn/problems/add-binary/description/
3.2 题目分析：
- 题目给出两个只包含二进制数字的字符串，要求返回其按二进制运算规则相加的和
- 该和用字符串表示
3.3 思路讲解：
模拟⼗进制中我们列竖式计算两个数之和的过程。但是这⾥是⼆进制的求和，我们不是逢⼗进⼀，⽽是逢⼆进⼀。
3.4 代码实现：
classSolution{public: string addBinary(string a, string b){int cur1=a.size()-1,cur2=b.size()-1; string ret="";//返回的字符串int t=0;//进位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;}};第四章：字符串乘法
4.1 题目链接：https://leetcode.cn/problems/multiply-strings/description/
4.2 题目分析：
- 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
- 观察字符串长度范围，首先排除正常乘法，因为其值大小远超long long所能表示的范围
4.3 思路讲解：
整体思路就是模拟我们⼩学列竖式计算两个数相乘的过程。但是为了我们书写代码的⽅便性，我们选择⼀种优化版本的，就是在计算两数相乘的时候，先不考虑进位，等到所有结果计算完毕之后，再去考虑进位。如下图：
4.4 代码实现：
classSolution{public: string multiply(string num1, string num2){int m=num1.size(),n=num2.size(); string ret="";int len=m+n-1;reverse(num1.begin(),num1.end());reverse(num2.begin(),num2.end());//先逆序两个字符串//不进位的乘法 vector<int>temp(len);for(int i=0;i<m;i++){for(int j=0;j<n;j++){ temp[i+j]+=(num1[i]-'0')*(num2[j]-'0');//此处注意是+=}}//处理进位int t=0,cur=0;while(cur<len||t){if(cur<len){ t+=temp[cur++];} ret+=t%10+'0'; t/=10;}//处理前导0while(ret.size()>1&&ret.back()=='0'){ ret.pop_back();}reverse(ret.begin(),ret.end());return ret;}};尾声：字里行间的永恒智慧
字符串算法，如同文字的魔法，将字符编织成信息的纽带。从暴力匹配到前缀树，从压缩算法到加密技术，它展示了算法的艺术与科学的结合。在未来的旅程中，字符串算法将继续书写信息时代的传奇，为人类探索未知的语言和数据世界提供智慧的钥匙。
本篇关于字符串算法的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！
