43. 字符串相乘

思路：

模拟竖向除法，一些边界情况需要考虑到，需要提前把相乘结果的最大位数预留出来，最后根据实际情况进行缩减，同时进位的时候也需要考虑最高位的进位。

代码

class Solution {
public:
    string multiply(string num1, string num2) {
        // 模拟数学方法

        // 确保num1是较长的
        if (num1.size() < num2.size()) {
            swap(num1, num2);
        }
        int l1 = num1.size(), l2 = num2.size();
        string ret(l1 + l2, '0');  // 最坏情况长度是l1+l2，有些情况可能不是，需要删除高位多余的0
        for (int i = l2 - 1; i >= 0; -- i) {  // nums2从后往前遍历，
            int count = 0;  // 进位值
            for (int j = l1 - 1; j >= 0; -- j) {  // nums2从后往前遍历
                int sum = (num1[j] - '0') * (num2[i] - '0') + count;  // 两数相乘 + count
                sum += (ret[(l2 - i) + (l1 - j) - 2] - '0');  // 这个数字加上原先ret对应位的数
                ret[(l2 - i) + (l1 - j) - 2] = '0' + sum % 10;  // 取余
                count = sum / 10;  // 求进位
            }
            if (count != 0) {  // 如果不等于0，说明高位需要存放这个，也即为j=-1时候，
                ret[(l2 - i) + (l1 - -1) - 2] = '0' + count;
            }
        }
        
        // 去除高位多余的0，但是当结果位0时候，要确保至少有一个0
        while (ret.size() > 1 && ret.back() == '0') {
            ret.pop_back();
        }
        reverse(ret.begin(), ret.end());
        return ret;

    }
};