目录
- 一、[最长公共前缀](https://leetcode.cn/problems/longest-common-prefix/description/)
- 二、[最长回文子串](https://leetcode.cn/problems/longest-palindromic-substring/description/)
- 三、[二进制求和](https://leetcode.cn/problems/add-binary/description/)
- 四、[字符串相乘](https://leetcode.cn/problems/multiply-strings/description/)
- 结尾
一、最长公共前缀
题目描述：
思路讲解：
本题需要找到所有字符串的公共前缀，那么我们可以先找到两个字符串的公共前缀，再跟其他字符串得到新的公共前缀，重复这个操作，最终找到所有字符串的公共前缀。
除了比较两个字符串的方式，还可以同时比较所有字符串，我们可以先找到最短字符串并记录它的长度，我们使用这个长度用来遍历所有字符串，就不会出现越界的情况，每遍历1位，就判断当前位上所有字符串上的字符是否相同，相同则向后遍历，不相同或是遍历完后则返回前面部分。
编写代码：
class Solution {
public:string longestCommonPrefix(vector<string>& strs) {string ans;int strsLen = strs.size();int MinStrLen = 201; // 记录最短for(int i = 0 ; i < strsLen ;i++){int strLen = strs[i].size();MinStrLen = MinStrLen < strLen ? MinStrLen : strLen;}for(int i = 0 ; i < MinStrLen ;i++){char ch = strs[0][i];for(int j = 0 ; j < strsLen ; j++){if(ch != strs[j][i])return ans;}ans += ch;}return ans;}
};
二、最长回文子串
题目描述：
思路讲解：
本题的暴力解法是找出字符串的所有子字符串，判断这些子字符串中有哪些字符串是符合回文规则的，并找到最长的一条返回，按照这个思路来讲，本题的时间复杂度将会达到O(n3)，并不是一个很好的解法。
本题我们使用中心扩展算法来解决本题，首先定义一个中心点在数组的最左边，在定义两个变量来记录回文字符串的左右边界的下标，然后从中心点向两边延展，若两个位置的字符相同则继续向两边延展，当两个位置的字符不相同或是其中一边越界，与目前最长的回文字符串作比较，大于则更新新回文字符串的左右边界的下标，小于等于则不做处理，再将中心点向右移动，再重复上面的操作。
上面的操作只针对了回文字符串为奇数的情况，若为偶数的情况，则选最左边两个相邻的两个点作为中心点，然后从中心点向两边延展，重复上面的操作。
编写代码：
class Solution {
public:string longestPalindrome(string s) {int sLen = s.size();int MaxLeft = 0 , MaxRight = 0;for(int i = 0 ; i < sLen ; i++){// 回文为奇数个的情况int left = i , right = i;// 当两个字母相同向两边延伸while((left >= 0 && right < sLen) && s[left] == s[right]){left--;right++;}// 不相同时,判断与之前最长回文串的长度作比较if(right - left - 2> MaxRight - MaxLeft){MaxLeft = left + 1;MaxRight = right - 1;}// 回文为偶数个的情况left = i , right = i + 1;// 当两个字母相同向两边延伸while(left >= 0 && right < sLen && s[left] == s[right]){left--;right++;}// 不相同或越界时,判断与之前最长回文串的长度作比较if(right - left - 2 > MaxRight - MaxLeft){MaxLeft = left + 1;MaxRight = right - 1;}}return s.substr(MaxLeft , MaxRight - MaxLeft + 1);}
};
三、二进制求和
题目描述：
思路讲解：
本题的思路是将两个字符串逆转，然后将两个字符串就从低位开始相加，得到的字符串反转后得到答案。
编写代码：
class Solution {
public:string addBinary(string a, string b) {reverse(a.begin(),a.end());reverse(b.begin(),b.end());string ans;int aLen = a.size() , bLen = b.size();int add = 0; // 代表进位for(int i = 0 ; i < aLen || i < bLen || add; i++){int num1 = i < aLen ? a[i] - '0' : 0;int num2 = i < bLen ? b[i] - '0' : 0;int sum = num1 + num2 + add;add = sum / 2;ans += (sum % 2) + '0';}reverse(ans.begin(),ans.end());return ans;}
};
四、字符串相乘
题目描述：
思路讲解：
解法一：“模拟”列竖式运算
将num1和num2逆转，定义一个字符串str来记录答案，定义一个字符串tmp记录num2中每一个数字乘num1得到的字符串，并将tmp与str相加，当得到的所有tmp都相加以后，需要注意的是这里我们将num1和num2逆转以后再计算的，所以这里的str是逆序的，所以再将str逆转就可以得到答案。
使用这个方法有三个细节点：
- 高位相乘时，需要补上"0"
- 处理前导0，当两个字符串中有一个位0就返回0
- 需要将得str逆转得到答案
解法二：无进位相乘然后相加，最后处理进位
将num1和num2逆转，定义两个变量n，m分别记录num1和num2的长度，那么num1和num2相乘得到结果的长度必定为n+m-1，定义一个数组int tmp[n+m-1]记录结果中每一个位置的无进位相乘的结果，将num1中的每一位与num2中的每一位相乘，得到的结果放入到tmp中，放入tmp中位置的计算公式为num1当前数字下标与num2当前数字下标相加，当相乘完后，再处理数组tmp的进位，定义一个字符串ans来记录处理tmp得到的结果，需要注意的是这里我们将num1和num2逆转以后再计算的，所以这里的ans是逆序的，我们需要逆转ans才能得到最终的答案。
使用这个方法有三个细节点：
- 计算相乘时，加入到tmp位置的计算方式
- 处理前导0，当两个字符串中有一个位0就返回0
- 需要将得ans逆转得到答案
编写代码：
class Solution {
public:string multiply(string num1, string num2) {int numLen1 = num1.size();int numLen2 = num2.size();if((numLen1 == 1 && num1[0] == '0') || numLen2 == 1 && num2[0] == '0' )return "0";reverse(num1.begin(),num1.end());reverse(num2.begin(),num2.end());vector<int> v(numLen1 + numLen2 - 1);for(int i = 0 ; i < numLen1 ; i++){for(int j = 0 ; j < numLen2 ; j++){v[i+j] += (num1[i] - '0') * (num2[j] - '0');}}int add = 0;string ans;for(int i = 0 ; i < v.size() ; i++){int sum = v[i] + add;add = sum / 10;ans += to_string(sum % 10);}while(add){ans += to_string(add % 10);add /= 10;}reverse(ans.begin(),ans.end());return ans;}
};
结尾
如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，希望大家给一个三连支持一下！！🌹🌹
