0+111头像

算法 --字符串

字符串算法题，本质上就是“数组操作”加上“字符编码转换”以及“人类手工计算过程的代码化”。

例题剖析

题目一：最长公共前缀

解法一：

class Solution {
public:
    string longestCommonPrefix(vector<string>& 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);
    }
};

代码逻辑解析

这段代码采用了逐个比较的思想：

  1. 初始化：string ret = strs[0];
    将结果字符串 ret 初始化为字符串数组中的第一个字符串。这是一个常见的策略，把第一个字符串当作“基准”。

  2. 遍历数组：for (int i = 1; i < strs.size(); i++)
    从第二个字符串开始，依次遍历数组中的每一个字符串。

  3. 寻找公共部分：ret = findCommon(ret, strs[i]);
    对于每一个遍历到的字符串 strs[i]，调用 findCommon 函数来求它与当前 ret 的最长公共前缀，并将结果更新回 ret。这意味着 ret 的长度会随着遍历过程不断缩短，最终保留下来的就是所有字符串的公共前缀。

  4. 辅助函数 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(vector<string>& 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];
    }
};

代码逻辑解析

这段代码的核心思想是：同时比较所有字符串的同一列（同一个索引位置）。

  1. 外层循环（列遍历）：for(int i = 0; i < strs[0].size(); i++)
    以第一个字符串 strs[0] 作为基准。循环变量 i 代表当前正在比较的字符索引（列）。因为公共前缀不可能比第一个字符串还长，所以以它的长度作为循环上限。

  2. 取基准字符：char tmp = strs[0][i];
    取出第一个字符串在第 i 个位置的字符，作为这一列的对比基准。

  3. 内层循环（行遍历）：for(int j = 1; j < strs.size(); j++)
    从第二个字符串开始，依次遍历数组中的其他所有字符串，检查它们在第 i 个位置的字符。

  4. 不匹配检测与返回：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 的部分，这正是当前找到的最长公共前缀。

  5. 循环结束返回：return strs[0];
    如果外层循环完整执行完毕，都没有触发内层的提前返回，说明第一个字符串 strs[0] 就是所有字符串的公共前缀，直接返回它即可。

复杂度分析

  • 时间复杂度：O(N×M)。最坏情况下（所有字符串完全相同），需要比较每一个字符串的每一个字符。其中 N 是字符串数量，M 是字符串平均长度。

  • 空间复杂度：O(1)（不计返回值占用的空间）。只使用了常数个额外变量。

算法对比（纵向扫描 vs 两两比较）

  • 解法二：

    • 优点：在发现不匹配时能尽早退出。例如输入是 ["abcdefg", "abcde", "abc"]，当 i=3（即比较第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);
    }

    // 返回 {起始索引, 长度}
    pair<int, 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());
        vector<int> 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 = 9801，2+2=4位）。
但因为 i 最大为 m-1，j 最大为 n-1，所以 i+j 最大为 m+n-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(M+N)。主要是 tmp 数组和结果字符串 ret 占用的空间。

这段代码它将复杂的进位逻辑剥离了出来。如果我们在双层循环里直接处理进位，代码会变得异常复杂且容易出错（因为一个乘积可能会影响后面好几个位）。而“先全部乘完累加，最后统一处理进位”的思路，将问题分成了两个简单的子问题，大大降低了编码难度。

注意事项

写字符串代码时，90% 的 Bug 都出在以下细节上：

  1. 空字符串与边界检查

    • 永远要先判断字符串是否为空（s.empty() 或 s.length() == 0）。例如求最长公共前缀时，如果数组为空，直接访问 strs[0] 会导致程序崩溃。

  2. 索引与长度的“差一错误”

    • 长度为 n 的字符串，有效索引是 0 到 n-1。

    • 在中心扩展算法中，循环结束后的真实回文长度通常是 right - left - 1，真实起始位置是 left + 1，这里极容易算错。

  3. 字符与整数的转换

    • 字符 '0' 到 '9' 的 ASCII 码是连续的。数字字符转整数用 c - '0'，整数转字符用 n + '0'。

    • 判断字符是否为字母或数字，可以使用 C++ 内置函数 isalnum(c)、isdigit(c)、isalpha(c)。

  4. 字符串拼接的性能陷阱

    • 在 C++ 中，s = s + c 在循环中会产生大量临时对象，导致时间复杂度退化到 O(N2)，容易超时。

    • 正确做法：使用 s += c 或 s.push_back(c)。如果是倒序生成的字符串（如大数运算），最后统一用 reverse(s.begin(), s.end()) 反转。

  5. 善用内置函数，但别滥用 substr

    • C++ 的 string 提供了很多好用的函数，如 find()、substr()、reverse()。

    • 但 substr() 会创建新的字符串对象，在循环中频繁使用会导致性能下降。能用索引解决的就尽量用索引。

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2501_94405739/article/details/167805462

文章来源转载

评论

评论列表

微信小程序
QQ小程序

关于作者

点赞数：0
关注数：0
粉丝：0
文章：0
关注标签：0
加入于：--