【每日算法】专题十_字符串

1. 算法思路

1.公共前缀类问题

• 水平扫描：以首个字符串为初始基准，逐个与后续字符串比较，不断缩小公共前缀范围，直到遍历完所有字符串或前缀为空。
• 垂直扫描：按列依次检查所有字符串同一位置的字符是否一致，遇到不匹配或字符串结束时停止，返回已匹配的前缀部分。

2. 回文相关问题

• 中心扩展：遍历每个字符，分别以该字符为中心（奇数长度）或以该字符与下一个字符为中心（偶数长度）向两侧扩展，记录最长回文的起始位置和长度。

3. 字符串加法

• 双指针逆序处理：从两个字符串的最低位（末尾）开始，逐位相加并维护进位，处理长度差异和剩余进位，最后反转结果得到正确顺序。

4. 字符串乘法

• 模拟竖式乘法：逆序遍历两个字符串的每一位，逐位相乘后将结果累加至对应位置，处理进位，最后去除前导零得到最终结果。

通用技巧

• 逆序遍历：适用于需从低位开始处理的场景（如加法、乘法），简化位对齐逻辑。
• 进位管理：用变量记录进位值，确保每一步的进位被正确传递到高位。
• 边界处理：遍历字符串时注意防止越界，对长度不一致的情况做兼容（如短字符串剩余位视为 0）。
• 特殊情况预处理：如空字符串、全零输入等，提前处理以减少无效计算。
• 结果修正：通过反转、去除前导零等操作，确保输出格式正确。

复杂度特点

• 时间复杂度：多为 O (n²) 或 O (n*m)（n、m 为字符串长度），取决于遍历次数和字符比较次数。
• 空间复杂度：通常为 O (n)（用于存储结果）或 O (1)（仅用常数空间），需根据结果存储需求评估。

2. 例题

2.1 最长公共前缀

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

方法一：水平扫描法

• 核心思路：先假设第一个字符串是最长公共前缀（LCP），然后逐个与后续字符串比较，不断缩小公共前缀的范围，直到遍历完所有字符串或前缀为空。
• 优势：实现简单，适用于字符串长度相近或公共前缀较短的情况。

方法二：垂直扫描法

• 核心思路：按列处理，依次检查所有字符串同一位置的字符是否相同，遇到不匹配或字符串结束时立即停止，返回已匹配的前缀部分。
• 优势：更高效，尤其在字符串长度差异较大时，无需检查所有字符。

方法对比

• 水平扫描法：依次比较相邻字符串，逐步缩小公共前缀范围。实现简单，适合字符串长度相近或公共前缀较短的场景。
• 垂直扫描法：按列检查所有字符串的相同位置字符，遇到不匹配或字符串结束时停止。效率更高，尤其适用于字符串长度差异较大的场景。

 

    string longestCommonPrefix(vector<string>& strs) {// 方法一// int n = strs.size();// string ret = strs[0];// for(int i = 1; i < n; ++i)//     ret = common_prefix(ret, strs[i]);// return ret;// 方法2for(int i = 0; i < strs[0].size(); ++i){char ch = strs[0][i];for(int j = 1; j < strs.size(); ++j){if(i >= strs[j].size() || strs[j][i] != ch)return strs[0].substr(0, i);}}return strs[0];}// string common_prefix(string& s1, string& s2)// {//     int i = 0;//     while(i < min(s1.size(), s2.size()) && s1[i] == s2[i]) ++i;//     return s1.substr(0, i);// }

2.2 最长回文子串

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

核心思路：

使用中心扩展法来寻找字符串中的最长回文子串。核心思路如下：

1. 遍历每个字符作为回文中心：对于字符串中的每个位置 i，分别以该位置为中心（奇数长度回文）或以该位置和下一个位置为中心（偶数长度回文）进行扩展。

2. 中心扩展过程：

   • 奇数长度回文：从 left = i 和 right = i 开始，向两边扩展，检查 s[left] 和 s[right] 是否相等。
   • 偶数长度回文：从 left = i 和 right = i+1 开始，向两边扩展，检查对称性。

3. 记录最长回文：每次扩展结束后，计算当前回文子串的长度（right - left - 1），并更新最长回文的起始位置 begin 和长度 len。

4. 返回结果：遍历结束后，截取从 begin 开始、长度为 len 的子串即为最长回文。

关键点：

• 时间复杂度：O (n²)，其中 n 是字符串长度。每个位置最多扩展 n 次。
• 空间复杂度：O (1)，仅需常数空间。
• 处理边界：通过 left >= 0 和 right < s.size() 确保扩展过程不会越界。

该算法通过枚举所有可能的回文中心并向两边扩展，有效找到最长回文子串。

 

    string longestPalindrome(string s) {// 中心扩展算法int begin = 0, len = 0;for(int i = 0; i < s.size(); ++i){// 奇数扩展int left = i, right = i;while(left >= 0 && right < s.size() && s[left] == s[right])--left, ++right;if(len < right - left - 1){len = right - left - 1;begin = left + 1;}// 偶数扩展left = i, right = i + 1;while(left >= 0 && right < s.size() && s[left] == s[right])--left, ++right;if(len < right - left - 1){len = right - left - 1;begin = left + 1;}}return s.substr(begin, len);}

2.3 二进制求和

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

核心思路：

使用双指针法实现二进制字符串相加，核心思路如下：

1. 逆序处理：从两个二进制字符串的最低位（最右侧）开始逐位相加，使用指针 i 和 j 分别指向字符串 a 和 b 的末尾。

2. 处理进位：维护一个进位变量 carry，初始为 0。每次将当前位的数值（0 或 1）与 carry 相加，得到总和 sum。

3. 计算当前位结果：

   • sum % 2 得到当前位的二进制值（0 或 1），转换为字符后追加到结果字符串 ret 中。
   • sum / 2 得到新的进位值（0 或 1），更新 carry。

4. 处理长度差异和剩余进位：

   • 使用 while(i >= 0 || j >= 0 || carry > 0) 确保所有位和进位都被处理。
   • 若某字符串已遍历完（如 i < 0），则该位视为 0。

5. 反转结果：由于逐位追加的结果是逆序的，最后需反转 ret 得到正确顺序的二进制和。

关键点：

• 时间复杂度：O (max (n, m))，其中 n 和 m 分别是字符串 a 和 b 的长度。
• 空间复杂度：O (max (n, m))，主要用于存储结果字符串。
• 进位处理：通过 carry > 0 确保最高位的进位被正确处理（如 "1" + "1" 需产生进位）。

该算法通过逐位相加和进位处理，高效地实现了二进制字符串的加法运算。

 

    string addBinary(string a, string b) {string ret;int carry = 0;int i = a.size() - 1, j = b.size() - 1;while(i >= 0 || j >= 0 || carry > 0){if(i >= 0) carry += a[i--] - '0';if(j >= 0) carry += b[j--] - '0';ret += (carry % 2) + '0';carry /= 2;}reverse(ret.begin(), ret.end());return ret;}

2.4 字符串相乘

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

核心思路：

使用模拟乘法竖式的方法实现字符串形式的大数乘法，核心思路如下：

1. 预处理零值：若任一输入为 "0"，直接返回 "0"。

2. 结果数组初始化：创建长度为 num1.size() + num2.size() 的结果字符串 ret（初始全为 '0'），因为两数相乘的长度最大为两数长度之和。

3. 逐位相乘与累加：

   • 逆序遍历：从最低位（最右侧）开始逐位相乘，模拟手算乘法。
   • 计算乘积：num1[i] 与 num2[j] 的乘积对应结果的 i+j+1 位（低位对齐）。
   • 处理进位：当前乘积 mul 与 ret[i+j+1] 累加后，更新当前位 i+j+1 的值（取模），并将进位加到 i+j 位（通过字符直接相加实现进位累积）。

4. 结果处理：

   • 去除前导零：通过 find_first_not_of('0') 找到第一个非零字符位置，截取子串。
   • 返回结果：截取后的子串即为最终乘积。

关键点：

• 时间复杂度：O (n*m)，其中 n 和 m 分别为 num1 和 num2 的长度。
• 空间复杂度：O (n+m)，用于存储结果数组。
• 位置映射：num1[i] 和 num2[j] 的乘积对应结果的 i+j 和 i+j+1 位，确保低位对齐。
• 进位累积：通过字符直接相加（如 ret[i + j] += sum / 10）隐式处理进位累积，避免额外循环。

该算法通过模拟竖式乘法，将每一步的乘积和进位准确映射到结果数组的对应位置，高效实现了大数乘法。

 

    string multiply(string num1, string num2) {if(num1 == "0" || num2 == "0") return "0";string ret(num1.size() + num2.size(), '0');for(int i = num1.size() - 1; i >= 0; --i){for(int j = num2.size() - 1; j >= 0; --j){int mul = (num1[i] - '0') * (num2[j] - '0');int sum = ret[i + j + 1] - '0' + mul;ret[i + j + 1] = sum % 10 + '0';ret[i + j] += sum / 10;}}size_t start = ret.find_first_not_of('0');return ret.substr(start);}