字符串模拟题精选：思维与实现解析

解法二：统一比较

使用 char 类型变量记录字符串中的元素，通过循环逐个比较字符是否相等。考虑到'最长公共前缀'的上限，当某段完全相同的字符串长度等于当前遍历的字符串长度时，说明已经达到了公共前缀的上限，此时可以直接返回结果。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        // 解法二：统计比较
        if (strs.empty()) return "";
        for (int j = 0; j < strs[0].size(); j++) {
            char ch = strs[0][j];
            for (int i = 0; i < strs.size(); i++) {
                if (j == strs[i].size() || strs[i][j] != ch) {
                    return strs[0].substr(0, j);
                }
            }
        }
        return strs[0];
    }
};

最长回文子串

题目链接： LeetCode 5. 最长回文子串

中心扩展算法

回文数具有对称特性，我们可以固定一个中心点，从中心开始向两边扩展。注意需要同时考虑奇数长度和偶数长度的回文情况。扩展过程中，若遇到越界或不符合回文性质时，停止并返回。

class Solution {
public:
    string longestPalindrome(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++;
            }
            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);
    }
};

二进制求和

题目链接： LeetCode 67. 二进制求和

高精度模拟加减乘除

这道题本质上是高精度加法。我们模拟列竖式计算过程，对于两个字符串的处理从低位开始。需要特别注意进位处理逻辑，并且要处理前导零的情况。

数字字符转换为整型时：数字字符 - '0' 即得到整型值。最后，使用 reverse 进行翻转，以符合题目的要求。

class Solution {
public:
    string addBinary(string a, string b) {
        int cur1 = a.size() - 1, cur2 = b.size() - 1;
        int t = 0;
        string ret;
        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;
    }
};

字符串相乘

题目链接： LeetCode 43. 字符串相乘

模拟小学列竖式运算

关于此类高精度题目，推荐先将原始字符串进行反转，因为列竖式计算是从低位开始的。对于两个字符串，先反转它们，再将数字字符转换为整型，通过数组存储结果。我们创建的数组大小为 m + n - 1，其中 m 和 n 分别是两个字符串的长度。通过数学分析，可以发现这个刚好满足累加所需的存储空间。

这里采用无进位相乘然后相加，最后再处理进位。由于无论是先进行进位还是后进行进位，最终的结果是相同的，因此我们推荐先将结果存储下来，然后再进行进位处理，这样更为方便和简洁，避免了细节很多存在的问题。

算法步骤：

1. 将输入的两个字符串反转，以便从低位开始进行处理。
2. 对于两个字符串中的数字，通过下标相加，其两个数字结果正好对应数组中相应位置的值。在进行加法时，需使用 += 来累加结果。
3. 在处理完所有操作后，可能会出现前导零的情况。最终需要使用 reverse 进行翻转，并去掉多余的前导零。

class Solution {
public:
    string multiply(string nums1, string nums2) {
        int n = nums1.size(), m = nums2.size();
        // 字符串反转
        reverse(nums1.begin(), nums1.end());
        reverse(nums2.begin(), nums2.end());
        
        vector<int> nums(m + n - 1);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                nums[i + j] += ((nums1[i] - '0') * (nums2[j] - '0'));
        
        // 进位处理
        string ret;
        int t = 0, cur = 0;
        while (cur < m + n - 1 || t) {
            if (cur < m + n - 1) t += nums[cur++];
            ret += t % 10 + '0';
            t /= 10;
        }
        
        // 处理前导零
        while (ret.size() > 1 && ret.back() == '0') ret.pop_back();
        reverse(ret.begin(), ret.end());
        return ret;
    }
};