字符串算法篇——字里乾坤，算法织梦，解构字符串的艺术（下）

前言

   上篇我们先容了常用的字符串及其相干原理应用，本篇将联合具体标题，进一步深化对于字符串算法的把握运用。
  第一章：最长公共前缀

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

1.2 标题分析：

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

1.3 思绪解说：

解法⼀（两两⽐较)：
我们可以先找出前两个的最⻓公共前缀，然后拿这个最⻓公共前缀依次与后⾯的字符串⽐较，如许就可以找出全部字符串的最⻓公共前缀。\
解法⼆（统⼀⽐较）：
题⽬要求多个字符串的公共前缀，我们可以逐位⽐较这些字符串，哪⼀位出现了差异，就在哪⼀位截⽌。
1.4 代码实现：

两两比力代码示例：

1. class Solution
2. {
3. public:
4. string longestCommonPrefix(vector<string>& strs)
5. {
6. // 解法⼀：两两⽐较
7. string ret = strs[0];
8. for(int i = 1; i < strs.size(); i++)
9. ret = findCommon(ret, strs[i]);
10. return ret;
11. }
12. string findCommon(string& s1, string& s2)
13. {
14. int i = 0;
15. while(i < min(s1.size(), s2.size()) && s1[i] == s2[i]) i++;
16. return s1.substr(0, i);
18. }
19. };

复制代码

同一比力代码示例：

1. class Solution {
2. public:
3.     string longestCommonPrefix(vector<string>& strs) {
4.         //所有字符串一起 逐个比较
5.         string ret=strs[0];
6.         for(int i=0;i<ret.size();i++)
7.         {
8.             char temp=strs[0][i];
9.             for(int j=1;j<strs.size();j++)
10.             {
11.                
12.                 if(i==strs[j].size()||temp!=strs[j][i])
13.                 {
14.                     return ret.substr(0,i);
15.                 }
16.             }
17.         }
18.         return ret;
19.         
20.     }
21. };

复制代码

第二章：最长回文子串

2.1 标题链接：https://leetcode.cn/problems/longest-palindromic-substring/description/

2.2 标题分析：

标题要求找出字符串s中的最长回文子串，我们先来回顾一下什么是回文串。
   回文串：即正反情势雷同的字符串，比方aba
  2.3 思绪解说：

本题我们可以采取中心拓展算法

• 对于⼀个⼦串⽽⾔，如果它是回⽂串，而且⻓度⼤于 2，那么将它⾸尾的两个字⺟去除之后，它仍然是个回⽂串。云云如许去除，⼀直除到⻓度⼩于便是 2 时呢？⻓度为 1 的，⾃⾝与⾃⾝就构成回⽂；⽽⻓度为 2 的，就要判定这两个字符是否相当了。
  
• 从这个性子可以反推出来，从回⽂串的中⼼开始，往左读和往右读也是⼀样的。那么，是否可以摆列回⽂串的中⼼呢？
  
• 从中⼼向两边扩展，如果两边的字⺟雷同，我们就可以继承扩展；如果差异，我们就停⽌扩展。
  
• 如许只必要⼀层 for 循环，我们就可以完成先前两层 for 循环的⼯作量。
  

2.4 代码实现：

1. class Solution {
2. public:
3.     string longestPalindrome(string s) {
4.         int n=s.size();
5.         int left=0,right=0,len=0,begin=0;
6.         for(int i=0;i<n;i++)
7.         {
8.             //奇数次拓展
9.             left=i,right=i;
10.             while(left>=0&&right<n&&s[left]==s[right])
11.             {
12.                 left--;
13.                 right++;
14.             }
15.             if(right-left-1>len)
16.             {
17.                 begin=left+1;
18.                 len=right-left-1;
20.             }
21.            
22.             //偶数次拓展
23.             left=i,right=i+1;
24.             while(left>=0&right<n&&s[left]==s[right])
25.             {
26.                 left--;
27.                 right++;
28.             }if(right-left-1>len)
29.             {
30.                 begin=left+1;
31.                 len=right-left-1;
33.             }
34.             
35.         }
36.         return s.substr(begin,len);
37.         
38.     }
39. };

复制代码

第三章：二进制求和

3.1 标题链接：https://leetcode.cn/problems/add-binary/description/

3.2 标题分析：

• 标题给出两个只包罗二进制数字的字符串，要求返回其按二进制运算规则相加的和
  
• 该和用字符串体现
  

3.3 思绪解说：

模拟⼗进制中我们列竖式盘算两个数之和的过程。但是这⾥是⼆进制的求和，我们不是逢⼗进⼀，⽽是逢⼆进⼀。
3.4 代码实现：

1. class Solution {
2. public:
3.     string addBinary(string a, string b) {
4.         int cur1=a.size()-1,cur2=b.size()-1;
5.         string ret="";//返回的字符串
6.         int t=0;//进位
7.         while(cur1>=0||cur2>=0||t)
8.         {
9.             if(cur1>=0)
10.             {
11.                 t+=a[cur1--]-'0';
12.             }
13.             if(cur2>=0)
14.             {
15.                 t+=b[cur2--]-'0';
16.             }
17.             ret+=t%2+'0';
18.             t/=2;
19.         }
20.         reverse(ret.begin(),ret.end());
21.         return ret;
22.         
23.     }
24. };

复制代码

第四章：字符串乘法

4.1 标题链接：https://leetcode.cn/problems/multiply-strings/description/

4.2 标题分析：

• 给定两个以字符串情势体现的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也体现为字符串情势。
  
• 观察字符串长度范围，起首清除正常乘法，由于其值巨细远超long long所能体现的范围
  

4.3 思绪解说：

团体思绪就是模拟我们⼩学列竖式盘算两个数相乘的过程。但是为了我们誊写代码的⽅便性，我们选择⼀种优化版本的，就是在盘算两数相乘的时间，先不思量进位，比及全部结果盘算完毕之后，再去思量进位。如下图：

4.4 代码实现：

1. class Solution {
2. public:
3.     string multiply(string num1, string num2) {
4.         int m=num1.size(),n=num2.size();
5.         string ret="";
6.         int len=m+n-1;
7.         reverse(num1.begin(),num1.end());
8.         reverse(num2.begin(),num2.end());//先逆序两个字符串
9.         //不进位的乘法
10.         vector<int> temp(len);
11.         for(int i=0;i<m;i++)
12.         {
13.             for(int j=0;j<n;j++)
14.             {
15.                 temp[i+j]+=(num1[i]-'0')*(num2[j]-'0');//此处注意是+=
16.             }
17.         }
18.         //处理进位
19.         int t=0,cur=0;
20.         while(cur<len||t)
21.         {
22.             if(cur<len)
23.             {
24.             t+=temp[cur++];
25.             }
26.             ret+=t%10+'0';
27.             t/=10;
28.         }
29.         //处理前导0
30.         while(ret.size()>1&&ret.back()=='0')
31.         {
32.             ret.pop_back();
33.         }
34.         reverse(ret.begin(),ret.end());
35.         return ret;
36.         
37.     }
38. };

复制代码

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

   字符串算法，犹如笔墨的邪术，将字符编织成信息的纽带。从暴力匹配到前缀树，从压缩算法到加密技能，它展示了算法的艺术与科学的联合。在将来的路程中，字符串算法将继承誊写信息期间的传奇，为人类探索未知的语言和数据天下提供智慧的钥匙。
  本篇关于字符串算法的先容就暂告段落啦，渴望能对各人的学习产生资助，接待各位佬前来支持斧正！！！