凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 43. Multiply Strings

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


题目

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note:

  • The numbers can be arbitrarily large and are non-negative.
  • Converting the input string to integer is NOT allowed.
  • You should NOT use internal library such as BigInteger.

题意

给出两个以字符串形式表示的数字,求出其结果的字符串形式。

解法

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;
    }
};