前言
本文将结合具体题目，深化对于字符串算法的掌握运用。
第一章：最长公共前缀
1.1 题目描述
现给出字符串数组，要求返回所有字符串的最长公共前缀。
1.2 思路讲解
解法一（两两比较）： 我们可以先找出前两个的最长公共前缀，然后拿这个最长公共前缀依次与后面的字符串比较，这样就可以找出所有字符串的最长公共前缀。
解法二（统一比较）： 题目要求多个字符串的公共前缀，我们可以逐位比较这些字符串，哪一位出现了不同，就在哪一位截止。
1.3 代码实现
两两比较代码示例：
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++;
}
return s1.substr(0, i);
}
};
统一比较代码示例：
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
// 所有字符串一起 逐个比较
string ret = strs[0];
for (int i = 0; i < ret.size(); i++) {
char temp = strs[0][i];
for (int j = 1; j < strs.size(); j++) {
if (i == strs[j].size() || temp != strs[j][i]) {
return ret.substr(0, i);
}
}
}
return ret;
}
};
第二章：最长回文子串
2.1 题目描述
题目要求找出字符串 s 中的最长回文子串。回文串即正反形式相同的字符串，例如 aba。
2.2 思路讲解
本题可以采用中心拓展算法。
- 对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。如此这样去除，一直除到长度小于等于 2 时呢？长度为 1 的，自身与自身就构成回文；而长度为 2 的，就要判断这两个字符是否相等了。
- 从这个性质可以反推出来，从回文串的中心开始，往左读和往右读也是一样的。那么，是否可以枚举回文串的中心呢？
- 从中心向两边扩展，如果两边的字母相同，我们就可以继续扩展；如果不同，我们就停止扩展。
- 这样只需要一层 for 循环，我们就可以完成先前两层 for 循环的工作量。
2.3 代码实现
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
int left = 0, right = 0, len = 0, begin = 0;
for (int i = 0; i < n; i++) {
// 奇数次拓展
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);
}
};
第三章：二进制求和
3.1 题目描述
题目给出两个只包含二进制数字的字符串，要求返回其按二进制运算规则相加的和，该和用字符串表示。
3.2 思路讲解
模拟十进制中我们列竖式计算两个数之和的过程。但是这里是二进制的求和，不是逢十进一，而是逢二进一。
3.3 代码实现
class Solution {
public:
string addBinary(string a, string b) {
int cur1 = a.size() - 1, cur2 = b.size() - 1;
string ret = "";
int 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;
}
};
第四章：字符串乘法
4.1 题目描述
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
观察字符串长度范围，首先排除正常乘法，因为其值大小远超 long long 所能表示的范围。
4.2 思路讲解
整体思路就是模拟我们小学列竖式计算两个数相乘的过程。为了书写代码的方便性，选择一种优化版本，就是在计算两数相乘的时候，先不考虑进位，等到所有结果计算完毕之后，再去考虑进位。
4.3 代码实现
class Solution {
public:
string multiply(string num1, string num2) {
int m = num1.size(), n = num2.size();
string ret = "";
int len = m + n - 1;
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
// 先逆序两个字符串
// 不进位的乘法
vector<int> temp(len);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
temp[i + j] += (num1[i] - '0') * (num2[j] - '0');
}
}
// 处理进位
int t = 0, cur = 0;
while (cur < len || t) {
if (cur < len) {
t += temp[cur++];
}
ret += t % 10 + '0';
t /= 10;
}
// 处理前导 0
while (ret.size() > 1 && ret.() == ) {
ret.();
}
(ret.(), ret.());
ret;
}
};
