目录
题目一——14. 最长公共前缀 - 力扣（LeetCode）
1.1.两两比较
1.2.统一比较
题目二——5. 最长回文子串 - 力扣（LeetCode）
2.1.中心拓展算法
题目三——67. 二进制求和 - 力扣（LeetCode）
题目四——43. 字符串相乘 - 力扣（LeetCode）
虽然说，我们这里是简单的介绍字符串的题目一般是怎么做，但是不太会深入介绍更多的字符串的算法
题目一——14. 最长公共前缀 - 力扣（LeetCode）
1.1.两两比较
我们可以两两比较得到我们的两个字符串的最长公共前缀，再将这个公共前缀和其他字符串进行再次查询公共前缀
class Solution {
public:
std::string longestCommonPrefix(std::vector<std::string>& strs) {
// 如果字符串向量为空，直接返回空字符串
// 但在这个实现中，我们假设向量至少包含一个字符串
// 并使用第一个字符串作为初始的公共前缀
std::string ret = strs[0];
// 遍历字符串向量中的每一个字符串（从第二个开始）
for (int i = 1; i < strs.size(); i++) {
// 更新公共前缀为当前公共前缀和当前字符串的公共部分
ret = findCommon(ret, strs[i]);
// 如果在某个点公共前缀变为空字符串，则无需继续比较，因为空字符串是最短的前缀
// 但在这个实现中，我们保持循环以展示完整的逻辑
// 在实际应用中，可以提前退出循环以提高效率
}
// 返回最终的公共前缀
return ret;
}
// 定义一个辅助函数，用于找出两个字符串的公共前缀
std::string findCommon(std::string& s1, std::string& s2) {
int i = 0;
// 遍历两个字符串，直到达到其中一个字符串的末尾或发现不匹配的字符
while (i < std::min(s1.size(), s2.size()) && s1[i] == s2[i]) {
i++;
}
// 返回s1中从开头到第一个不匹配字符之前的子串
// 这个子串就是s1和s2的公共前缀
return s1.substr(0, i);
}
};在C++中，std::string 类的 substr 成员函数用于获取一个字符串的子串。函数原型通常如下：
std::string substr(size_t pos = 0, size_t len = npos) const;
- pos 是子串开始的起始位置（基于0的索引）。如果省略，默认为0，即从字符串的开头开始。
- len 是要提取的字符数。如果省略，或者其值大于从 pos 到字符串末尾的字符数，则 substr 会提取从 pos 开始到字符串末尾的所有字符。
举个例子：
std::string s1 = "hello, world!"; size_t cur = 5; std::string result = s1.substr(0, cur); // 此时，result 的值将是 "hello"在这个例子中，我们从
s1的开头提取了5个字符，得到了子串"hello"。
1.2.统一比较
class Solution {
public:
std::string longestCommonPrefix(std::vector<std::string>& strs) {
// 如果字符串向量为空，理论上应该返回一个空字符串，
// 但在这个实现中，我们假设向量至少包含一个字符串，
// 并且以第一个字符串为基准进行比较。
// 外层循环遍历第一个字符串的每一个字符
for (int i = 0; i < strs[0].size(); i++) {
// 获取当前正在比较的字符（来自第一个字符串）
char tmp = strs[0][i];
// 内层循环遍历除第一个字符串外的其他所有字符串
for (int j = 1; j < strs.size(); j++) {
// 检查当前字符索引i是否超出了其他字符串的长度，
// 或者当前字符在其他字符串中是否与tmp不同。
if (i == strs[j].size() || tmp != strs[j][i]) {
// 如果满足上述任一条件，说明当前字符不是公共前缀的一部分，
// 因此返回当前已经确认的公共前缀（即strs[0]的前i个字符）。
// 使用substr函数从strs[0]的开头截取到第i个字符（不包含第i个字符）。
return strs[0].substr(0, i);
}
}
}
// 如果外层循环顺利结束，说明第一个字符串的所有字符
// 在其他所有字符串中都找到了匹配，因此第一个字符串本身就是公共前缀。
return strs[0];
}
};
题目二——5. 最长回文子串 - 力扣（LeetCode）
2.1.中心拓展算法
这个其实是借鉴了暴力解法和回文。
枚举每⼀个可能的⼦串⾮常费时，有没有⽐较简单⼀点的⽅法呢？
对于⼀个⼦串⽽⾔，如果它是回⽂串，并且⻓度⼤于2，那么将它⾸尾的两个字⺟去除之后，它仍然是 个回⽂串。
如此这样去除，⼀直除到⻓度⼩于等于2时呢？
- ⻓度为1的，⾃⾝与⾃⾝就构成回⽂；
- ⽽⻓度为2的，就要判断这两个字符是否相等了。
从这个性质可以反推出来，从回⽂串的中⼼开始，往左读和往右读也是⼀样的。
那么，是否可以枚举 回⽂串的中⼼呢？
从中⼼向两边扩展，
- 如果两边的字⺟相同，我们就可以继续扩展；
- 如果不同，我们就停⽌扩展。
这样 只需要⼀层for循环，我们就可以完成先前两层for循环的⼯作量
中心扩展算法是一种用于寻找最长回文子串的有效方法，它的核心思想是从可能的中心点开始，向两边扩展以检查是否存在回文子串，并记录找到的最长回文子串的位置和长度。
以下是中心扩展算法的具体思想：
- 枚举中心点：
- 在一个字符串中，回文子串可以是以单个字符为中心（形成奇数长度的回文子串）或以两个字符之间的空隙为中心（形成偶数长度的回文子串）。
- 因此，我们需要遍历字符串的每个字符以及每个字符之间的空隙，将它们作为潜在的中心点。
- 向两边扩展：
- 对于每个中心点，我们尝试向两边扩展，检查左右两侧的字符是否相等。
- 如果相等，则继续扩展；如果不相等，则停止扩展。
- 记录最长回文子串：
- 在扩展过程中，我们跟踪当前回文子串的长度，并将其与之前找到的最长回文子串的长度进行比较。
- 如果当前回文子串更长，则更新最长回文子串的起始位置和长度。
- 返回结果：
- 遍历完所有中心点后，我们得到了最长回文子串的起始位置和长度。
- 使用这些信息，我们可以从原始字符串中截取最长回文子串并返回。
在中心扩展算法中，我们区分奇数和偶数长度的回文子串，因为它们的中心点略有不同，并且这会影响我们如何向两边扩展来检查回文。
- 奇数长度的回文子串：
- 中心点是一个具体的字符。
- 我们从这个字符开始，分别向它的左侧和右侧扩展，检查左右两侧的字符是否相等。
- 例如，在字符串"ababa"中，"aba"是一个奇数长度的回文子串，它的中心点是字符'b'。
- 偶数长度的回文子串：
- 中心点位于两个字符之间的空隙。
- 我们从这两个字符开始，分别向它们的左侧和右侧扩展，同样检查左右两侧的字符是否相等。
- 例如，在字符串"abba"中，"bb"是一个偶数长度的回文子串，它的中心点是位于'a'和'b'之间的空隙。
class Solution {
public:
std::string longestPalindrome(std::string s) {
// 中心扩展算法：通过枚举所有可能的中心点，然后向两边扩展来寻找最长的回文子串
int begin = 0, len = 0; // 用于记录最长回文子串的起始位置和长度
int n = s.size(); // 字符串的长度
// 遍历字符串，依次枚举所有的中心点（包括字符和字符之间的空隙）
for (int i = 0; i < n; i++) {
// 奇数长度的回文子串扩展：以当前字符为中心点
int left = i, right = i; // 初始化左右指针为当前字符的位置
// 向两边扩展，直到字符不相等或达到字符串边界
while (left >= 0 && right < n && s[left] == s[right]) {
left--; // 左指针向左移动
right++; // 右指针向右移动
}
// 计算当前扩展得到的回文子串的长度
// 因为left和right在不相等或越界时会停止，这个时候left和right指向的字符都不是回文字符串的一部分
int currentLen = right - left + 1 - 2;
// 如果当前回文子串长度大于之前记录的最长长度，则更新记录
if (currentLen > len) {
begin = left + 1; // 更新最长回文子串的起始位置
len = currentLen; // 更新最长回文子串的长度
}
// 偶数长度的回文子串扩展：以当前字符和下一个字符之间的空隙为中心点
left = i, right = i + 1; // 初始化左右指针为当前字符和下一个字符的位置
// 向两边扩展，直到字符不相等或达到字符串边界
while (left >= 0 && right < n && s[left] == s[right]) {
left--; // 左指针向左移动
right++; // 右指针向右移动
}
// 同样计算当前扩展得到的回文子串的长度，并更新记录（如果需要）
// 因为left和right在不相等或越界时会停止，这个时候left和right指向的字符都不是回文字符串的一部分
currentLen = right - left +1 - 2;
if (currentLen > len) {
begin = left + 1; // 更新最长回文子串的起始位置
len = currentLen; // 更新最长回文子串的长度
}
}
// 根据记录的起始位置和长度，从原字符串中截取最长回文子串并返回
return s.substr(begin, len);
}
};
题目三——67. 二进制求和 - 力扣（LeetCode）
这道题主要考的主要是考高精度加法。
其实本质上考的是模拟加法的过程，这个思想和2. 两数相加 - 力扣（LeetCode）的是一模一样的。大家可以去这里看算法思想：链表算法题——进阶篇-CSDN博客
class Solution
{
public:
string addBinary(string a, string b)
{
string ret; // 初始化结果字符串
// 初始化两个指针，分别指向字符串a和b的末尾
// 这是因为我们要从字符串的低位（右边）开始相加
int cur1 = a.size() - 1, cur2 = b.size() - 1, t = 0;
// t用于存储进位
// 当两个字符串都还有字符未处理，或者存在进位时，继续循环
while(cur1 >= 0 || cur2 >= 0 || t)
{
// 如果a还有字符，将其对应的字符（'0'或'1'）转换为整数并加到t上
if(cur1 >= 0) t += a[cur1--] - '0';
// 如果b还有字符，同样将其对应的字符转换为整数并加到t上
if(cur2 >= 0) t += b[cur2--] - '0';
// 将当前位的和（模2）添加到结果字符串中
// 因为模2的结果只能是0或1，所以这里直接加上'0'字符就可以得到正确的字符表示
ret += t % 2 + '0';
// 更新进位值，为下一次循环做准备
t /= 2;
}
// 因为我们是从低位开始相加的，所以结果字符串是反的
// 需要将其反转才能得到正确的二进制表示
reverse(ret.begin(), ret.end());
// 返回相加后的二进制字符串
return ret;
}
};
题目四——43. 字符串相乘 - 力扣（LeetCode）
这道题目又是算乘法的啊！！算法思想其实和上面差不多
整体思路就是模拟我们⼩学列竖式计算两个数相乘的过程。但是为了我们书写代码的⽅便性，我们选 择⼀种优化版本的，就是在计算两数相乘的时候，先不考虑进位，等到所有结果计算完毕之后，再去 考虑进位。如下图：
class Solution
{
public:
string multiply(string n1, string n2)
{
// 解法概述：首先进行无进位相乘并累加结果，然后处理进位，最后处理可能的前导零
int m = n1.size(), n = n2.size();
// 将两个字符串反转，以便从低位开始相乘，这样可以方便地处理进位
reverse(n1.begin(), n1.end());
reverse(n2.begin(), n2.end());
// 创建一个向量来存储每一位相乘的累加结果（包括进位前的结果）
// 向量长度为m + n - 1，因为两个长度分别为m和n的数相乘的结果长度最多为m + n - 1
vector<int> tmp(m + n - 1, 0); // 初始化为0，避免未定义行为
// 1. 无进位相乘后相加
// 遍历n1和n2的每一位，将对应位置的字符转换为整数后相乘，并累加到tmp数组的对应位置上
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');
// 2. 处理进位
// 初始化当前处理的tmp数组索引和进位值
int cur = 0, t = 0;
string ret; // 用于存储最终结果
// 遍历tmp数组，处理每一位的进位
// 当还有未处理的tmp数组元素或存在进位时，继续循环
while(cur < m + n - 1 || t)
{
// 如果当前索引有效，则加上该索引处的值
if(cur < m + n - 1) t += tmp[cur++];
// 将当前位的值（模10）转换为字符并添加到结果字符串中
ret += t % 10 + '0';
// 更新进位值，为下一次循环做准备
t /= 10;
}
// 3. 处理前导零
// 如果结果字符串的最后一个字符是'0'，并且结果字符串长度大于1，则删除最后一个字符
// 这个操作在循环中进行，直到结果字符串不再以'0'结尾或长度变为1
while(ret.size() > 1 && ret.back() == '0') ret.pop_back();
// 由于之前反转了输入字符串，所以最后需要将结果字符串反转回来
reverse(ret.begin(), ret.end());
// 返回最终结果字符串
return ret;
}
}; 
