【基础算法总结】字符串篇

一，算法简介

字符串 string 是一种数据结构，它一般和其他的算法结合在一起操作，比如和模拟，高精度加减，双指针，动态规划等算法结合，所以有关字符串类的题型是多种多样的。通过本篇文章挑选的一些题目来熟悉有关字符串接口的使用。

二，算法原理和代码实现

14.最长公共前缀

算法原理：
这道题的本质是模拟，一般有以下两种模拟方法：

解法1：两两字符串比较。
可以封装一个函数用来找出两个字符串的最长公共前缀。固定一个字符串，用另一个字符串的每个字符和固定字符串的每个字符进行比较，保存相同的字符，直到其中一个字符串截止或是字符不相等，最后返回保存的字符串即可。

假设有 n 个字符串，每个字符串的平均长度为 m，则时间复杂度是 O(n*m)。

代码实现：

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){string tmp = "";// 比较两两字符串的每个字符，返回相同的部分。直到一个结束或不相等int n = min(s1.size(), s2.size());for(int i = 0; i < n; i++)if(s1[i] == s2[i]) tmp += s1[i];else break;return tmp;}
};

解法2：统一比较
把每个字符串从头开始每个字符同时比较，保存相同字符(或是保存对应的下标，获取结果时直接截取)，直到有一个字符串遍历结束或是字符不相等。

假设有 n 个字符串，每个字符串的平均长度为 m，则时间复杂度也是 O(n*m)。

细节问题：

这里有一个选谁作为参考的问题：
我们可以选第一个字符串作为参考。第一层循环的结束条件用第一个字符串的长度，第二层循环比较字符是否相等时也用第一个字符串的每个字符作参考，如果某一个长度越界了或是字符不相同了就截取。

代码实现：

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.最长回文子串

算法原理：

解法：中心拓展算法
中心拓展算法的本质是使用双指针进行暴力枚举，只不过是根据回文子串的特性枚举的。
算法流程：
(1) 遍历字符串，依次固定每一个字符作为中心 i
(2) 从中心点开始，使用双指针 left 和 right，当两者不越界并且两个字符相等时，同时向两边扩展。

细节问题：

奇数长度和偶数长度都需要考虑。
先定义变量 begin 为回文串的起始长度，len 为回文串的长度。
(1) 奇数长度的扩展
定义 left 和 right 作为回文子串边界的下一个位置，left = right = i，若 left 和 right 不越界，且s[left] == s[right]，则 left–，right++。
当跳出循环，且left 和 right之间的长度 > len 时，就要更新 begin 和 len。
(2) 偶数长度的扩展
让 left = i，right = i + 1，其他的与奇数长度的扩展一致。

代码实现：

class Solution 
{
public:string longestPalindrome(string s) {int n = s.size();int begin = 0, len = 0;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);}
};

67.二进制求和

算法原理：

本题是一个二进制的高精度加法模拟题，本质是模拟加法的列竖式运算。

代码实现：

class Solution 
{
public:string addBinary(string a, string b) {int i = a.size() - 1, j = b.size() - 1, t = 0;string ret = "";while(i >= 0 || j >= 0 || t){if(i >= 0) t += (a[i--] - '0');if(j >= 0) t += (b[j--] - '0');ret += (t % 2 + '0');t /= 2;}reverse(ret.begin(), ret.end());return ret;}
};

43.字符串相乘

算法原理：
本题是一道高精度乘法的模拟题。

解法1：模拟竖式乘法运算
先把两个字符串逆序，固定一个字符，遍历另一个与它相乘。思路很好想，但是代码不好写，有很多细节。
细节问题：
(1) 高位相乘的时候要补"0"
(2) 处理前导0

(3) 注意最后结果的逆序

解法2：对解法1做优化，先无进位相乘再相加，最后处理进位。
这个解法的核心是要借助一个辅助数组。假设两个字符串的长度是m，n，则创建一个大小为 m+n-1的数组，再用两层for循环模拟竖式乘法计算出每一个相乘的值，把每个值都扔进数组中的对应位置，并且把每次相乘的值和原来对应位置的值相加，最后再处理进位。

图解1如下：

在这里插入图片描述

图解2如下：
在这里插入图片描述

代码实现：

class Solution 
{
public:string multiply(string num1, string num2) {// 准备工作int n = num1.size(), m = num2.size();vector<int> add(n+m-1);reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());// 无进位相乘再相加,放入数组的对应位置for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)add[i+j] += ((num1[i] - '0') * (num2[j] - '0'));// 处理进位，把数组里的值相加int t = 0, i = 0;string ret = "";while(i < n+m-1 || t){if(i < n+m-1) t += add[i++];ret += to_string(t % 10);t /= 10;}// 处理前导0reverse(ret.begin(), ret.end());if(ret[0] == '0') return "0";return ret;}
};