算法学习（十）—— 字符串

关于字符串操作

这类题一般是和其它算法合起来，比如模拟，双指针，动态规划或者回溯等，所以字符串相关的题目类型一般是非常非常丰富的，这里我们选取几道经典的题目进行讲解

部分OJ题详解

14. 最长公共前缀

14. 最长公共前缀 - 力扣（LeetCode）

题目题意还是很简单的，就是返回单词的公共前缀，没有公共前缀就返回空，下面来分析下这道题：

• 解法一：两两比较，找公共前缀；假设有四个字符串，分成三组，每两组找公共前缀，然后再两个前缀再找公共前缀，最终结果就是所有字符串的公共前缀，这道题我们主要就是解决“如何找到两个字符串的公共前缀”，很简单，定义两个指针即可
• 解法二：统一比较；就是定义一个指针，然后一次性比较所有字符串的前缀，当有空或者有一个字符不一样，停止遍历，返回结果。

解法一： 

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++;//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() || tmp != strs[j][i])return strs[0].substr(0, i);}return strs[0];}
};

5. 最长回文字串

5. 最长回文子串 - 力扣（LeetCode）

题目要我们找出一个字符串s中的最长回文字串，其中这个字串是一串连续的字串，下面我们来分析下这道题：

• 解法：中心扩展算法；这个算法的本质还是暴力枚举，但是这里是利用了回文串的特性来做枚举的，比正常枚举要快
• 我们先固定一个位置，假设为i，然后定义两个指针，向前向后移动，因为如果是回文，左边和右边的字符是对称的，所以指针移动的时候，如果指针指向的值相同，就继续移动，如果不一样了，记录结果
• 但是这样只能找奇数的回文字串，偶数的找不了，所以我们固定i，先left = right找奇数找一次，然后再right = left + 1，再找偶数找一次，就能把奇数偶数全找到
• 步骤：1，固定一个中心点    2，从中心开始，向两边扩展，奇数偶数各找一次

class Solution {
public:string longestPalindrome(string s) {int begin = 0, len = 0; for(int i = 0; i < s.size(); i++) //依次枚举所有的中点{//先找奇数的扩展int left = i, right = i;while(left >= 0 && right < s.size()){if(s[left] == s[right]){left--;right++;}elsebreak;}if(right - left - 1 > len){begin = left + 1;len = right - left - 1;}//再做偶数的扩展left = i, right = left + 1;while(left >= 0 && right < s.size()){if(s[left] == s[right]){left--;right++;}elsebreak;}if(right - left - 1 > len){begin = left + 1;len = right - left - 1;}}    return s.substr(begin, len);}
};

67. 二进制求和

67. 二进制求和 - 力扣（LeetCode）

这个题目是一道经典的算法题，用到的算法是“高精度加法”，而同样的还是高精度减法，乘法和触发。而高精度顾名思义就是一个数实在是太大，平常的数据类型存不下，然后我们要对这种很大的数字进行运算，用到的算法就是“高精度运算”

下面我们来分析下这道题：

• 解法：模拟列竖式运算。这道题和我们链表章节的“两数相加”那个题目很相似，我们定义一个t = 0记录相加的结果，具体步骤和链表的“两数相加”很像：算法学习（八） —— 链表-CSDN博客
• 

class Solution {
public:string addBinary(string a, string b) {string ret;int cur1 = a.size() - 1, cur2 = b.size() - 1, 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;}
};

43. 字符串相乘

43. 字符串相乘 - 力扣（LeetCode）

这一题用到的就是我们上一题提到的“高精度乘法”这个算法，题目很简单，就是把字符串的值相乘，注意不能使用stoi和to_string等字符串整型转换函数，因为这时题目要求的，下面来解释下这道题：

• 解法一：模拟列竖式运算；步骤一：单独拿nums2的一位和num1相乘    步骤而：再把所有的结果累加起来。
• 细节一：高位相乘的时候，要补0     细节二：处理前导0    细节三：注意计算结果的顺序（可以看到解法一思路很简单，但是细节很多很多，稍不注意就会出错，所以解法一的代码不太好写）
• 解法二：对解法一做优化 --> 五进位相乘再相加，最后处理进位
• 
• 对于步骤②，我们可以搞一个数组int[m + n - 1] tmp，m是num1的程度，n是num2的长度，然后我们就可以直接相加，因为同一列算出来的数存进数组时，下标是一样的，可以直接相加
• 对于步骤③，就是处理进位，就是遍历一次数组，然后一边累加再放到最终字符串ret里
• 细节：处理前导零 

 解法一的代码太复杂就不写了，我们直接用解法二来写：

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();vector<int> tmp(m + n - 1); //存储步骤②的结果，顺便实现相加//2，无进位相乘再相加for(int i = 0; i < m; i++){for(int j = 0; j < n; j++)tmp[i + j] += ((num1[i] - '0') * (num2[j] - '0'));}//3，处理进位int cur = 0, t = 0; //cur遍历数组，t表示进位string ret; //存储最终结果while(cur < m + n - 1 || t != 0){if(cur < m + n - 1) t += tmp[cur++];ret += (t % 10) + '0';t /= 10;}//4，处理前导零while(ret.size() > 1 && ret.back() == '0') ret.pop_back();reverse(ret.begin(), ret.end());return ret;}
};