【算法】字符串

快乐的流畅：个人主页

个人专栏：《算法神殿》《数据结构世界》《进击的C++》

远方有一堆篝火，在为久候之人燃烧！

---

引言

字符串题，大多数是模拟题，或者考察其他算法。通过本专题，了解字符串题型的函数接口和常用做法。

一、最长公共前缀

思路：

1. 先处理边界，数组为空，返回空串
2. 先用字符串tmp存储第一个字符串，再与其他字符串两两比较，保留相同的部分
3. 比较完后，最后保留下来的tmp，即为最长公共前缀

class Solution
{
public:string longestCommonPrefix(vector<string>& strs){if(strs.size() == 0) return "";string tmp = strs[0];for(int i=1; i<strs.size(); i++){int cur = 0;while(cur < tmp.size() && cur < strs[i].size() && tmp[cur] == strs[i][cur]){cur++;}tmp.resize(cur);}return tmp;}
};

二、最长回文子串

思路：

1. 中心扩展算法：暴力解法的优化，利用了回文串对称的性质进行枚举
2. 遍历字符串，对于每一个位置，分别进行奇数长度和偶数长度的枚举，分别进行结果更新
3. 注意遍历的过程中，只记录起始位置和长度，最后再创建子串

class Solution
{
public:string longestPalindrome(string s){int pos = 0, len = 0;for(int i=0; i<s.size(); i++){int left1 = i, right1 = i;//奇数个while(left1 >= 0 && right1 < s.size() && s[left1] == s[right1]){left1--;right1++;}if(right1 - left1 - 1 > len){pos = left1 + 1;len = right1 - left1 - 1;}int left2 = i, right2 = i + 1;//偶数个while(left2 >= 0 && right2 < s.size() && s[left2] == s[right2]){left2--;right2++;}if(right2 - left2 - 1 > len){pos = left2 + 1;len = right2 - left2 - 1;}}return s.substr(pos, len);}
};

三、二进制求和

思路：

1. 高精度加法
2. 分别从两个字符串的尾部开始向前遍历，模拟列竖式的过程
3. 如果cur1、cur2存在，则取出对应位置的数字，否则返回0
4. 将取出的数字与进位相加，再进行取模和整除操作，更新结果字符串和进位
5. 循环条件：两个字符串没遍历完或者进位不为0，只要有一个满足，则循环继续
6. 最后逆置字符串，返回

class Solution
{
public:string addBinary(string a, string b){string s;int cur1 = a.size() - 1, cur2 = b.size() - 1, carry = 0;while(cur1 >= 0 || cur2 >= 0 || carry){int n1 = cur1 >= 0 ? a[cur1--] - '0' : 0;int n2 = cur2 >= 0 ? b[cur2--] - '0' : 0;int n = n1 + n2 + carry;s += n % 2 + '0';carry = n / 2;}reverse(s.begin(), s.end());return s;}
};

四、字符串相乘

思路：

1. 高精度乘法
2. 先无进位相乘，再处理进位，最后处理前导零
3. 无进位相乘：开辟tmp数组，大小为m + n - 1，分别从两个字符串的尾部开始向前遍历，对应下标i + j，进行无进位相乘
4. 处理进位：从后向前遍历tmp数组，处理进位的同时更新结果字符串
5. 处理前导零：当结果字符串长度大于1，且尾部为零，尾删
6. 逆置字符串，返回

class Solution
{
public:string multiply(string n1, string n2){//无进位相乘int m = n1.size(), n = n2.size();vector<int> tmp(m + n - 1);for(int i=m-1; i>=0; i--){for(int j=n-1; j>=0; j--){tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');}}//处理进位string s;int cur = m + n - 2, carry = 0;while(cur >= 0 || carry){if(cur >= 0) carry += tmp[cur--];s += carry % 10 + '0';carry /= 10;}//去除前导零while(s.size() > 1 && s.back() == '0') s.pop_back();//逆序reverse(s.begin(), s.end());return s;}
};

真诚点赞，手有余香