凌云的博客

LeetCode 算法题 43. 字符串相乘

分类：algorithm| 发布时间：2016-10-10 10:33:00

---

题目

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

说明：

• num1 和 num2 的长度小于110。
• num1 和 num2 只包含数字 0-9。
• num1 和 num2 均不以零开头，除非是数字 0 本身。
• 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

解法 1

class Solution {
public:
    string multiply(string num1, string num2) {
        vector<int> ret(num1.size() + num2.size(), 0);
        const int size1 = num1.size() - 1, size2 = num2.size() - 1;
        for (int i = size1; i >= 0; --i) {
            for (int j = size2; j >= 0; --j) {
                int k = (size1 - i) + (size2 - j);
                ret[k] += (num1[i] - '0') * (num2[j] - '0');
                ret[k + 1] += ret[k] / 10;
                ret[k] %= 10;
            }
        }

        int i = ret.size() - 1;
        for (; i > 0 && !ret[i]; --i) ;

        string result;
        for (; i >= 0; --i) {
            result.push_back(ret[i] + '0');
        }

        return result;
    }
};

解法 2

class Solution {
public:
    string multiply(string num1, string num2) {
        vector<int> product(num1.size() + num2.size(), 0);
        for (int i = num1.size() - 1; i >= 0; --i) {
            for (int j = num2.size() - 1; j >= 0; --j) {
                int k = i + j + 1;
                int tmp = (num1[i] - '0') * (num2[j] - '0');
                product[k] += tmp % 10;
                product[k-1] += tmp / 10;
            }
        }

        // process carry
        for (int i = product.size() - 1; i > 0; --i) {
            if (product[i] >= 10) {
                product[i-1] += (product[i] / 10);
                product[i] %= 10;
            }
        }

        // get leftmost number index
        int k = 0;
        while (k < product.size() - 1 && !product[k]) ++k;

        string ret;
        ret.reserve(product.size() - k);
        for (; k < product.size(); ++k) {
            ret.push_back(product[k] + '0');
        }

        return ret;
    }
};