前言

上篇我们介绍了常用的字符串及其相关原理应用，本篇将结合具体题目，进一步深化对于字符串算法的掌握运用。

第一章：最长公共前缀

1.1 题目链接：https://leetcode.cn/problems/longest-common-prefix/description/

1.2 题目分析：

• 现给出字符串数组，要求返回所有字符串的最长公共前缀

1.3 思路讲解：

解法⼀（两两⽐较)：
我们可以先找出前两个的最⻓公共前缀，然后拿这个最⻓公共前缀依次与后⾯的字符串⽐较，这样就可以找出所有字符串的最⻓公共前缀。\

解法⼆（统⼀⽐较）：
题⽬要求多个字符串的公共前缀，我们可以逐位⽐较这些字符串，哪⼀位出现了不同，就在哪⼀位截⽌。

1.4 代码实现：

两两比较代码示例：

class Solution
{
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);}
};

统一比较代码示例：

class Solution {
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 代码实现：

class Solution {
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 代码实现：

class Solution {
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 代码实现：

class Solution {
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;}
};

尾声：字里行间的永恒智慧

字符串算法，如同文字的魔法，将字符编织成信息的纽带。从暴力匹配到前缀树，从压缩算法到加密技术，它展示了算法的艺术与科学的结合。在未来的旅程中，字符串算法将继续书写信息时代的传奇，为人类探索未知的语言和数据世界提供智慧的钥匙。

本篇关于字符串算法的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！