主页 > IT业界 >

字符串（典型算法思想）——OJ例题算法解析思路

IT业界
2025-09-08 12:57:01

一、14. 最长公共前缀 - 力扣（LeetCode）

解法一：算法代码（两两比较）

1. 初始化公共前缀

2. 遍历字符串数组

3. 辅助函数 findCommon

4. 返回最终结果

总结

解法二：算法代码（统一比较）

1. 初始化

2. 外层循环

3. 内层比较

4. 返回结果

总结

二、5. 最长回文子串 - 力扣（LeetCode）

算法代码：（中心扩散）

1. 初始化变量

2. 遍历每个字符

3. 奇数长度的回文扩展

4. 偶数长度的回文扩展

5. 返回结果

总结

三、67. 二进制求和 - 力扣（LeetCode）

算法代码：（模拟十进制的大数相加的过程）

1. 初始化变量

2. 逐位相加

3. 反转结果字符串

4. 返回结果

总结

四、43. 字符串相乘 - 力扣（LeetCode）

算法代码：（无进位相乘然后相加，最后处理进位）

1. 初始化和反转字符串

2. 无进位相乘

3. 处理进位

4. 处理前导零

5. 反转结果字符串

6. 返回结果

总结

一、14. 最长公共前缀 - 力扣（LeetCode）

解法一：算法代码（两两比较） 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); } };

1. 初始化公共前缀

选择第一个字符串：将数组中的第一个字符串 strs[0] 作为初始的公共前缀 ret。这是因为在比较多个字符串时，至少第一个字符串本身是一个候选的公共前缀。

2. 遍历字符串数组

逐个比较：使用一个循环，从第二个字符串（索引为 1）开始，逐个与当前的公共前缀 ret 进行比较，直到遍历完整个字符串数组。对于每个字符串，调用辅助函数 findCommon 来更新公共前缀。

3. 辅助函数 findCommon

比较两个字符串：在 findCommon 函数中，传入两个字符串 s1 和 s2。初始化一个索引 i 为 0。

逐字符比较：使用 while 循环逐字符比较 s1 和 s2：

循环条件是 i 小于 s1 和 s2 的最小长度，并且当前字符相同（s1[i] == s2[i]）。

当条件满足时，增加 i，表示当前公共前缀的长度。

返回公共前缀：使用 s1.substr(0, i) 返回 s1 的子串，即从头到当前公共前缀的长度 i 的部分。

4. 返回最终结果

返回公共前缀：当所有字符串都被比较过后，最终的公共前缀存储在 ret 中，函数返回这个结果。

总结

该算法通过逐对字符串的比较，逐步更新公共前缀，最终得到所有字符串的最长公共前缀。时间复杂度为 O(S)，其中 S 是所有字符串中字符的总数。这种方法简单直观，适合处理较小规模的字符串数组。

解法二：算法代码（统一比较） 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]; } };

1. 初始化

选择第一个字符串：代码通过遍历第一个字符串 strs[0] 的每个字符来作为公共前缀的基础。

2. 外层循环

逐字符遍历：使用一个外层循环遍历第一个字符串的每个字符，索引 i 表示当前字符的位置。

3. 内层比较

逐个比较其他字符串：在外层循环中，使用一个内层循环，从第二个字符串开始（索引 j），依次比较当前字符 tmp（即 strs[0][i]）与每个其他字符串的对应字符（strs[j][i]）。

条件检查：

如果 i 超出了当前字符串 strs[j] 的长度（即 i == strs[j].size()），或者当前字符 tmp 与 strs[j][i] 不相等，说明公共前缀到此为止，返回 strs[0] 从开始到 i 的子串（strs[0].substr(0, i)）。

4. 返回结果

无不匹配情况：如果外层循环完成而没有返回，意味着第一个字符串 strs[0] 本身就是所有字符串的公共前缀，直接返回 strs[0]。

总结

该算法通过统一比较的方式，逐字符检查所有字符串，能够高效地找到最长的公共前缀。时间复杂度为 O(S)，其中 S 是所有字符串中字符的总数。如果没有公共前缀，该方法也能在最坏情况下高效停止并返回结果。这个方法简洁且易于理解，适合处理较小规模的字符串数组。

二、5. 最长回文子串 - 力扣（LeetCode）

算法代码：（中心扩散） class Solution { public: string longestPalindrome(string s) { // 中⼼扩展算法 int begin = 0, len = 0, 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++; } 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); } };

1. 初始化变量

变量定义：

begin：用于记录最长回文子串的起始索引。

len：用于记录当前找到的最长回文子串的长度。

n：存储字符串 s 的长度。

2. 遍历每个字符

中心点枚举：使用一个循环遍历字符串 s 中的每个字符。每个字符可以视为回文的中心点，回文可以是奇数长度或偶数长度，因此需要处理这两种情况。

3. 奇数长度的回文扩展

设置左右指针：将 left 和 right 都初始化为当前字符的索引 i，表示以 s[i] 为中心的奇数长度回文。

扩展检查：使用一个 while 循环进行扩展，条件是 left 和 right 在字符串范围内，并且两个指针指向的字符相同。循环中向左右扩展 left-- 和 right++。

更新最长回文子串：在每次扩展后，如果找到的回文长度（right - left - 1）比当前记录的最长长度 len 更长，则更新 begin 和 len。

4. 偶数长度的回文扩展

设置左右指针：将 left 初始化为 i，right 初始化为 i + 1，表示以 s[i] 和 s[i + 1] 为中心的偶数长度回文。

扩展检查：同样使用 while 循环进行扩展，检查条件与之前相同。

更新最长回文子串：如果找到的回文长度更长，则更新 begin 和 len。

5. 返回结果

提取并返回最长回文子串：循环结束后，利用 s.substr(begin, len) 返回最长的回文子串。

总结

该算法通过中心扩展的方法，逐个检查每个字符作为回文中心的可能性，有效地检测出所有可能的回文子串。时间复杂度为 O(n²)，其中 n 是字符串的长度。此方法简单且直观，适合处理较短的字符串，能够很好地找到最长回文子串。

三、67. 二进制求和 - 力扣（LeetCode）

算法代码：（模拟十进制的大数相加的过程） class Solution { public: string addBinary(string a, string b) { string ret; int cur1 = a.size() - 1, cur2 = b.size() - 1, 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; } };

1. 初始化变量

结果字符串 ret：用于存储最终的二进制加法结果。

指针 cur1 和 cur2：初始化为字符串 a 和 b 的最后一位（即末尾字符），用于从后往前逐位相加。

进位变量 t：用于存储当前位的进位值，初始化为 0。

2. 逐位相加

循环条件：使用 while 循环，条件是 cur1 或 cur2 大于等于 0（表示还有位数未处理）或者进位 t 非零（表示最后一位的进位需要处理）。

处理每一位：

如果 cur1 大于等于 0，说明字符串 a 还有剩余位数，将 a[cur1]（当前位）转换为数字并加到进位 t 中，然后将 cur1 向左移动一位（--cur1）。

如果 cur2 大于等于 0，执行类似的操作，将 b[cur2] 加入进位，并将 cur2 向左移动一位。

计算当前位的结果：使用 t % 2 获取当前位的值（即和的最后一位），并将其转换为字符形式 '0' 或 '1'，然后将结果添加到字符串 ret 中。

更新进位：将 t 除以 2，计算下一位的进位。

3. 反转结果字符串

反转 ret：因为在计算过程中是从最低位开始添加结果到字符串 ret，最终需要将字符串反转，以获得正确的二进制表示。

4. 返回结果

返回最终结果：返回反转后的字符串 ret，即两个二进制字符串相加的结果。

总结

该算法通过模拟二进制加法的过程，逐位相加并处理进位，能够有效地计算出两个二进制字符串的和。时间复杂度为 O(max(m, n))，其中 m 和 n 分别是两个字符串的长度。这种方法简单直观，适合处理二进制字符串的加法运算。

四、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()); vector<int> tmp(m + n - 1); // 1. ⽆进位相乘后相加 for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) tmp[i + j] += (n1[i] - '0') * (n2[j] - '0'); // 2. 处理进位 int cur = 0, t = 0; string ret; while (cur < m + n - 1 || t) { if (cur < m + n - 1) t += tmp[cur++]; ret += t % 10 + '0'; t /= 10; } // 3. 处理前导零 while (ret.size() > 1 && ret.back() == '0') ret.pop_back(); reverse(ret.begin(), ret.end()); return ret; } };

1. 初始化和反转字符串

获取字符串长度：首先，获取输入字符串 n1 和 n2 的长度，分别用 m 和 n 表示。

反转字符串：将两个字符串反转，以便从低位到高位逐位相乘。这样可以简化乘法运算的过程。

2. 无进位相乘

创建临时数组：使用一个向量 tmp 来存储每一位相乘的结果。该数组的大小为 m + n - 1，足以存储所有可能的乘积。

逐位相乘：使用两个嵌套循环，外层循环遍历 n1 的每一位，内层循环遍历 n2 的每一位。对于每一对数字 n1[i]和 n2[j]，计算它们的乘积，并将结果累加到 tmp[i + j] 中。

3. 处理进位

初始化变量：使用变量 cur 来追踪 tmp 的当前索引，t 用于存储进位。

计算最终结果：使用 while 循环，条件为 cur 小于 m + n - 1 或者进位 t 非零。在每次循环中：

如果 cur 小于 m + n - 1，将 tmp[cur] 加入到 t 中，并自增 cur。

计算当前位的值 t % 10，并将其添加到结果字符串 ret 中（同样需要加上 '0' 转换为字符）。

更新进位 t，通过 t /= 10 获得新的进位值。