【算法】字符串相关
【ps】本篇有 4 道 leetcode OJ。
一、算法简介
字符串是一种数据结构，大多与别的算法结合在一起出题，例如模拟、高精度算法、双指针、dp、回溯等，因此这个专题的题型本身是特别丰富的。本篇选取了较为典型的字符串题型，除了涵盖一些常用算法，还包括经常用到的容器、接口等。
二、相关例题
1）最长公共前缀
14. 最长公共前缀
.1- 题目解析
我们可以对每个字符串进行两两比较，先找出一个公共前缀，再用这个公共前缀，与剩余的字符串进行两两比较，以此类推，直到得出最终结果。
当然，也可以进行统一的比较，用一个指针来遍历所有字符串，当指针所指位置的字符不相同时，就找出了公共前缀。
.2- 代码编写
//两两比较
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) {for(int i=0;i<strs[0].size();i++){char tmp=strs[0][i];for(int j=1;j<strs.size();j++){if(i==strs[j].size() || strs[j][i]!=tmp){return strs[0].substr(0,i);}}}return strs[0];}
};2）最长回文子串
5. 最长回文子串
.1- 题目解析
我们可以利用回文串的性质，先在字符串中固定一个中心位置，然后用两个指针从中心位置向左右两边扩展，直到找出两侧都不相等的字符为止。
.2- 代码编写
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,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）二进制求和
67. 二进制求和
.1- 题目解析
本题是一道高精度加法，只需模拟竖式计算的过程即可。
.2- 代码编写
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!=0){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());//由于+=操作，ret中的结果其实是倒序的，因此逆序操作一次return ret;}
};4）字符串相乘
43. 字符串相乘
.1- 题目解析
本题是一道高精度乘法，只需模拟竖式计算的过程即可。
在竖式的乘法中，第一个数会与第二个数的每一位分别相乘得到一个结果，然后将这些结果相加起来就可以得到最终结果了。
特别的，在进行高位相乘时，要在末位补上合适的 0。且在编写代码时，由于我们是低位向高位依此计算的，并将结果添加至一个字符串的末尾，因此模拟计算的结果其实是倒序的，我们还需要对其进行逆序操作。
不过，我们可以在模拟计算时，暂时先不处理进位，等到要将所有相乘的结果累加得出最终结果时，再统一处理进位。
具体的方式是，先用一个数组来存放所有相乘的结果，再模拟它们进位相加的过程。
另外，对于一些特殊的结果，还要处理它们的前导 0。
.2- 代码编写
class Solution {
public:string multiply(string num1, string num2) {//1.前期准备reverse(num1.begin(),num1.end());reverse(num2.begin(),num2.end());int m=num1.size(),n=num2.size();//2.先进位相乘，再相加vector<int> tmp(m+n-1);for(int i=0;i<m;i++){for(int j=0;j<n;j++){tmp[i+j]+=(num1[i]-'0')*(num2[j]-'0');}}//3.处理进位string ret;int cur=0,t=0;while(cur<m+n-1||t){if(cur<m+n-1)t+=tmp[cur++];ret+=t%10+'0';t/=10;}//4.处理前导0while(ret.size()>1 && ret.back()=='0')ret.pop_back();reverse(ret.begin(),ret.end());return ret;}
};