阅读量:0
文章目录
引言
字符串题，大多数是模拟题，或者考察其他算法。通过本专题，了解字符串题型的函数接口和常用做法。
一、最长公共前缀
思路：
- 先处理边界，数组为空，返回空串
- 先用字符串tmp存储第一个字符串，再与其他字符串两两比较，保留相同的部分
- 比较完后，最后保留下来的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; } }; 二、最长回文子串
思路：
- 中心扩展算法：暴力解法的优化，利用了回文串对称的性质进行枚举
- 遍历字符串，对于每一个位置，分别进行奇数长度和偶数长度的枚举，分别进行结果更新
- 注意遍历的过程中，只记录起始位置和长度，最后再创建子串
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); } }; 三、二进制求和
思路：
- 高精度加法
- 分别从两个字符串的尾部开始向前遍历，模拟列竖式的过程
- 如果cur1、cur2存在，则取出对应位置的数字，否则返回0
- 将取出的数字与进位相加，再进行取模和整除操作，更新结果字符串和进位
- 循环条件：两个字符串没遍历完或者进位不为0，只要有一个满足，则循环继续
- 最后逆置字符串，返回
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; } }; 四、字符串相乘
思路：
- 高精度乘法
- 先无进位相乘，再处理进位，最后处理前导零
- 无进位相乘：开辟tmp数组，大小为m + n - 1，分别从两个字符串的尾部开始向前遍历，对应下标i + j，进行无进位相乘
- 处理进位：从后向前遍历tmp数组，处理进位的同时更新结果字符串
- 处理前导零：当结果字符串长度大于1，且尾部为零，尾删
- 逆置字符串，返回
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; } }; 
