算法 --字符串

字符串算法题本质上就是“数组操作”加上“字符编码转换”以及“人类手工计算过程的代码化”。例题剖析题目一最长公共前缀解法一class Solution { public: string longestCommonPrefix(vectorstring strs) { if (strs.empty()) return ; 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); } };代码逻辑解析这段代码采用了逐个比较的思想初始化string ret strs[0];将结果字符串ret初始化为字符串数组中的第一个字符串。这是一个常见的策略把第一个字符串当作“基准”。遍历数组for (int i 1; i strs.size(); i)从第二个字符串开始依次遍历数组中的每一个字符串。寻找公共部分ret findCommon(ret, strs[i]);对于每一个遍历到的字符串strs[i]调用findCommon函数来求它与当前ret的最长公共前缀并将结果更新回ret。这意味着ret的长度会随着遍历过程不断缩短最终保留下来的就是所有字符串的公共前缀。辅助函数findCommon使用while循环条件是两个字符串都没有越界i min(s1.size(), s2.size())且当前字符相同s1[i] s2[i]。循环结束时i的值就是公共前缀的长度。最后通过s1.substr(0, i)截取并返回公共前缀。复杂度分析时间复杂度O(N×M)。其中 N 是字符串数组的长度M 是字符串的平均长度。最坏情况下需要比较所有字符串的每一个字符。空间复杂度O(1)不考虑返回值占用的空间。代码只使用了常数级别的额外变量i。解法二class Solution { public: string longestCommonPrefix(vectorstring strs) { if (strs.empty()) return ; 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]; } };代码逻辑解析这段代码的核心思想是同时比较所有字符串的同一列同一个索引位置。外层循环列遍历for(int i 0; i strs[0].size(); i)以第一个字符串strs[0]作为基准。循环变量i代表当前正在比较的字符索引列。因为公共前缀不可能比第一个字符串还长所以以它的长度作为循环上限。取基准字符char tmp strs[0][i];取出第一个字符串在第i个位置的字符作为这一列的对比基准。内层循环行遍历for(int j 1; j strs.size(); j)从第二个字符串开始依次遍历数组中的其他所有字符串检查它们在第i个位置的字符。不匹配检测与返回if(i strs[j].size() || tmp ! strs[j][i])这是代码中最关键的一步判断当前列是否终止i strs[j].size()这意味着字符串strs[j]的长度比i还要短已经越界了。既然某个字符串已经到头了那公共前缀最远也就只能到i了。tmp ! strs[j][i]当前对比的字符与基准字符不同说明公共前缀断了。如果满足上述任一条件立刻返回strs[0].substr(0, i)即截取第一个字符串从 0 开始长度为i的部分这正是当前找到的最长公共前缀。循环结束返回return strs[0];如果外层循环完整执行完毕都没有触发内层的提前返回说明第一个字符串strs[0]就是所有字符串的公共前缀直接返回它即可。复杂度分析时间复杂度O(N×M)。最坏情况下所有字符串完全相同需要比较每一个字符串的每一个字符。其中 N 是字符串数量M 是字符串平均长度。空间复杂度O(1)不计返回值占用的空间。只使用了常数个额外变量。算法对比纵向扫描 vs 两两比较解法二优点在发现不匹配时能尽早退出。例如输入是[abcdefg, abcde, abc]当i3即比较第4个字符d时内层循环发现i strs[2].size()长度为3索引最大为2立刻就能返回abc不需要像两两比较那样每次都截取一遍字符串。在数据量大、差异出现早的情况下效率往往更高。缺点如果第一个字符串特别长而其他字符串特别短内层循环的越界判断会频繁触发。解法一优点思路极其直观容易想到。缺点需要不断生成新的字符串对象substr会产生新对象可能会有额外的性能开销。题目二最长回文子串class Solution { public: string longestPalindrome(string s) { if (s.empty()) return ; int begin 0, len 0; // 依次枚举所有的中点 for (int i 0; i s.size(); i) { // 奇数长度 auto [l1, len1] expandAroundCenter(s, i, i); // 偶数长度 auto [l2, len2] expandAroundCenter(s, i, i 1); if (len1 len) { len len1; begin l1; } if (len2 len) { len len2; begin l2; } } return s.substr(begin, len); } // 返回 {起始索引, 长度} pairint, int expandAroundCenter(const string s, int left, int right) { while (left 0 right s.size() s[left] s[right]) { left--; right; } return {left 1, (right - 1) - (left 1) 1}; } };核心思想中心扩展算法回文串有一个天然的特性它是对称的。因此我们可以遍历字符串中的每一个字符把它当作回文串的“中心”然后向两边同时扩展看看能扩展多长。这里有一个关键点回文串的长度可能是奇数也可能是偶数。奇数长度如aba中心是一个字符。偶数长度如abba中心是两个字符之间的“缝隙”。这段代码正是分别处理了这两种情况。复杂度分析时间复杂度O(N2)。其中 N 是字符串的长度。我们遍历了 N 个中心点每个中心点向两边扩展最多需要 O(N)的时间。对于本题 N≤1000 的数据规模O(N2) 是可以接受的大约 100 万次操作。空间复杂度O(1)。只使用了常数级别的额外变量没有开辟与 N 相关的额外空间。题目三二进制求和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; } };核心思想模拟竖式加法逢二进一十进制的加法是逢十进一二进制则是逢二进一。我们需要从两个字符串的末尾最低位开始依次向前遍历逐位相加并处理进位。复杂度分析时间复杂度O(max(N,M))。其中 NN 和 MM 分别是字符串a和b的长度。我们最多只需要遍历较长的那个字符串一次。空间复杂度O(max(N,M))。主要消耗在存储结果字符串ret上。如果不算返回值额外的空间只有几个整型变量是 O(1)。题目四字符串相乘class Solution { public: string multiply(string num1, string num2) { int m num1.size(), n num2.size(); reverse(num1.begin(), num1.end()); reverse(num2.begin(), num2.end()); vectorint tmp(m n - 1); for (int i 0; i m; i) { for (int j 0; j n; j) { tmp[i j] (num1[i] - 0) * (num2[j] - 0); } } 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; } while (ret.size() 1 ret.back() 0) ret.pop_back(); reverse(ret.begin(), ret.end()); return ret; } };核心原理坐标映射假设有两个数字num1长度为m反转后记为n1索引i从 0 到m-1代表从低位到高位。num2长度为n反转后记为n2索引j从 0 到n-1代表从低位到高位。在竖式乘法中n1[i]和n2[j]相乘的结果应该放在最终结果的第i j位上。为了避开复杂的进位处理我们使用一个数组tmp来临时存储每个位置上的乘积之和暂时不管进位。数组tmp的最大长度是多少两个m位数和n位数相乘结果最多是m n位比如 99 * 99 9801224位。但因为i最大为m-1j最大为n-1所以ij最大为mn-2。因此初始化tmp大小为m n - 1就足够容纳所有累加结果了。辅助理解图无进位相乘累加阶段1 2 3 (n1反转后是 3, 2, 1) x 4 5 6 (n2反转后是 6, 5, 4) ----------------- 18 15 12 (3分别乘6,5,4放入tmp[0],tmp[1],tmp[2]) 27 22 8 (2分别乘6,5,4放入tmp[1],tmp[2],tmp[3]) 28 13 4 (1分别乘6,5,4放入tmp[2],tmp[3],tmp[4]) ----------------- 18 27 28 13 4 (这就是最终的tmp数组)注意此时tmp数组里存的数字是“错位相加”的结果还没有处理进位。统一处理进位现在我们得到了tmp [18, 27, 28, 13, 4]。从左到右从低位到高位处理进位。逻辑是当前位的值 tmp[cur] 上一轮的进位。保留个位作为结果十位作为进位传给下一位。处理前导零并反转ret 88065末尾是5没有多余的前导零。反转ret得到56088。返回结果56088。复杂度分析时间复杂度O(M×N)。双重循环遍历了两个字符串的所有位。对于本题 M,N≤200M,N≤200计算量大约在 4 万次左右运行极快。空间复杂度O(MN)。主要是tmp数组和结果字符串ret占用的空间。这段代码它将复杂的进位逻辑剥离了出来。如果我们在双层循环里直接处理进位代码会变得异常复杂且容易出错因为一个乘积可能会影响后面好几个位。而“先全部乘完累加最后统一处理进位”的思路将问题分成了两个简单的子问题大大降低了编码难度。注意事项写字符串代码时90% 的 Bug 都出在以下细节上空字符串与边界检查永远要先判断字符串是否为空s.empty()或s.length() 0。例如求最长公共前缀时如果数组为空直接访问strs[0]会导致程序崩溃。索引与长度的“差一错误”长度为n的字符串有效索引是0到n-1。在中心扩展算法中循环结束后的真实回文长度通常是right - left - 1真实起始位置是left 1这里极容易算错。字符与整数的转换字符0到9的 ASCII 码是连续的。数字字符转整数用c - 0整数转字符用n 0。判断字符是否为字母或数字可以使用 C 内置函数isalnum(c)、isdigit(c)、isalpha(c)。字符串拼接的性能陷阱在 C 中s s c在循环中会产生大量临时对象导致时间复杂度退化到 O(N2)容易超时。正确做法使用s c或s.push_back(c)。如果是倒序生成的字符串如大数运算最后统一用reverse(s.begin(), s.end())反转。善用内置函数但别滥用substrC 的string提供了很多好用的函数如find()、substr()、reverse()。但substr()会创建新的字符串对象在循环中频繁使用会导致性能下降。能用索引解决的就尽量用索引。