(很强的思路) LeetCode 43 : 字符串相乘

class Solution {
public:
    string multiply(string num1, string num2) {
        int len1 = num1.size();
        int len2 = num2.size();

        //两个数相乘, 乘机的位数不会超过这两个数的位数之和
        //创建一个保存结果的对象,长度为len1+len2, 初始化为全'0'
        string ret(len1 + len2, '0');

        //从个位开始, 循环相乘相加
        for(int i = len1 - 1; i >= 0; i--) {
            for(int j = len2 - 1; j >= 0; j--) {
                //过程比较抽象, 建议画个图跟着过程走一遍, 会很清晰
                int cur = (ret[i+j+1] - '0') + (num1[i] - '0') * (num2[j] - '0');
                ret[i+j+1] = cur % 10 + '0';
                ret[i + j] += cur / 10;
            }
        }

        //检查前面是否有0, 有的话截断
        for(int i = 0; i < len1 + len2; i++) {
            if( ret[i] != '0') {
                //从第一个不为0的数字开始截到最后一个数字, 即最后的结果
                //这里要么直接返回, 要么创建新的对象接收substr的值, 因为substr函数的返回值不是引用
                return ret.substr(i);
            }
        }
        //循环结束还没结束的话说明是全'0'
        return "0";
    }
};