LeetCode 0043 - Multiply Strings

Reck Zhang

发布于 2021-08-11 10:34:34

1430

发布于 2021-08-11 10:34:34

文章被收录于专栏：Reck ZhangReck Zhang

Multiply Strings

Desicription

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution

class Solution {
public:
    string multiply(string num1, string num2) {
        string res(num1.size() + num2.size(), '0');
        for(int i = num1.size()-1; i >= 0; i--){
            int carry = 0;
            for(int j = num2.size()-1; j >= 0; j--){
                int tmp = res[i+j+1] - '0' + (num1[i] - '0') * (num2[j] - '0') + carry;
                res[i+j+1] = tmp % 10 + '0';
                carry = tmp / 10;
            }
            res[i] += carry;
        }
        size_t index = res.find_first_not_of("0");
        if(index != string::npos)
            return res.substr(index);
        return "0";
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-11-11，如有侵权请联系 cloudcommunity@tencent.com 删除

biginteger