[Leetcode]43. Multiply Strings(C++)

题目描述

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

例子

例子 1

Input: num1 = “2”, num2 = “3” Output: “6”

例子 2

Input: num1 = “123”, num2 = “456” Output: “56088”

Note

The length of both num1 and num2 is < 110.

Both num1 and num2 contain only digits 0-9.

Both num1 and num2 do not contain any leading zero, except the number 0 itself.

You must not use any built-in BigInteger library or convert the inputs to integer directly.

解题思路

一个比较容易想到的思路是模拟我们进行多位乘法的过程中，主要需要两个函数：一个函数用于求一个多位数和一个一位数的乘积；一个函数用于求两个整数的和。通过模拟求乘法过程即可，注意在将不同位的乘积相加时注意高位的和需要根据位数添加相应 0 的个数，代码如下：

#include <algorithm>
#include <string>
#include <vector>

class Solution {
public:
    std::string multiply(std::string num1, std::string num2) {
        if (num1 == "0" || num2 == "0") return "0";

        std::vector<std::string> prods;
        for (int i = num1.length() - 1; i >= 0; i--) {
            std::string prod = multiplyOneDigit(num2, num1[i] - '0');
            prod += std::string(num1.length() - 1 - i, '0');
            prods.push_back(prod);
        }

        std::string result = prods[0];
        for (int i = 1; i < prods.size(); i++) {
            result = addTwoInt(result, prods[i]);
        }

        return result;
    }

private:
    std::string multiplyOneDigit(const std::string& num, int digit) {
        std::string result = "";
        int res = 0;
        for (int i = num.length() - 1; i >= 0; i--) {
            int prod = (num[i] - '0') * digit;
            std::string prod_s =
                std::to_string(prod) + std::string(num.length() - 1 - i, '0');
            result = addTwoInt(result, prod_s);
        }

        if (res > 0) {
            result += ('0' + res);
        }
        return result;
    }

    std::string addTwoInt(const std::string& num1, const std::string& num2) {
        std::string result = "";
        int ptr1 = num1.length() - 1, ptr2 = num2.length() - 1;
        int res = 0;
        while (ptr1 >= 0 || ptr2 >= 0) {
            int sum = 0;
            if (ptr2 >= 0) {
                sum += num2[ptr2] - '0';
            }
            if (ptr1 >= 0) {
                sum += num1[ptr1] - '0';
            }
            sum += res;
            res = 0;
            if (sum >= 10) {
                res = 1;
                sum -= 10;
            }
            ptr1--;
            ptr2--;
            result += ('0' + sum);
        }
        if (res > 0) {
            result += ('0' + res);
        }

        std::reverse(result.begin(), result.end());
        return result;
    }
};

时间复杂度: O(mn)
空间复杂度: O(mn)

GitHub 代码同步地址： 43.MultiplyStrings.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions