43. Multiply Strings

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

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contain only digits 0-9.
3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

---

把两个以字符串形式存储的非负整数相乘起来，输出字符串结果。很考验基本功的一个题目，使用小学学过的乘法来做，一位一位相乘，然后把每一位相乘的结果加起来得到最终结果。 比如35*423，先调个位置423*35，确保num2长度短于num1，然后我们循环num2的每一位，比如首先5*423=2115，然后3*423=1269，但是加起来的时候要注意，1269要往前缩进一位成12690。最终结果为2115+12690=14805。 所以整个过程需要实现两个辅助函数，两个字符串相加，以及一个字符和字符串相乘的函数。完整代码如下：

class Solution {
public:
    string add(string num1, string num2)
    {
        int i = num1.size() – 1, j = num2.size() – 1;
        string ans = "";
        bool carry = false;
        while (i >= 0 || j >= 0) {
            int sum = (i >= 0 ? (num1[i] – ‘0’) : 0) + (j >= 0 ? (num2[j] – ‘0’) : 0);
            sum += carry ? 1 : 0;
            if (sum >= 10) {
                ans.push_back(sum – 10 + ‘0’);
                carry = true;
            }
            else {
                ans.push_back(sum + ‘0’);
                carry = false;
            }
            i–;
            j–;
        }
        if (carry)
            ans.push_back(‘1’);
        reverse(ans.begin(), ans.end());
        return ans;
    }
    string multiply(string num1, char c)
    {
        if (c == ‘0’)
            return "0";
        if (c == ‘1’)
            return num1;
        string ans = "";
        int i = num1.size() – 1;
        int carry = 0;
        while (i >= 0) {
            int prod = (num1[i] – ‘0’) * (c – ‘0’);
            prod += carry;
            if (prod >= 10) {
                ans.push_back(prod % 10 + ‘0’);
                carry = prod / 10;
            }
            else {
                ans.push_back(prod + ‘0’);
                carry = 0;
            }
            i–;
        }
        if (carry > 0)
            ans.push_back(carry + ‘0’);
        reverse(ans.begin(), ans.end());
        return ans;
    }
    string multiply(string num1, string num2)
    {
        if (num1.size() < num2.size()) { // 确保num1长于num2 string tmp = num2; num2 = num1; num1 = tmp; } string ans = "0"; int j = num2.size() – 1, k = 0; // k:缩进的位数 while (j >= 0) { string p = multiply(num1, num2[j]); for (int i = 0; i < k; i++) p.push_back(‘0’); ans = add(ans, p); j–; k++; } return ans; } };

本代码提交AC，用时26MS。

二刷。上述解法不够简洁，讨论区有一种很漂亮的解法：https://discuss.leetcode.com/topic/30508/easiest-java-solution-with-graph-explanation/60，图片解释如下：

也就是可以算出来两个digit相乘的结果在最终结果中的下标位置，比如上图中123*45，num1的2乘以num2的4的结果是8，对应的下标分别是num1的i=1和num2的j=0，两个digit相乘结果最多可以占两位，这两位在最终结果中的下标是i+j和i+j+1，这个例子就是i+j=1,j+j+1=2，相乘结果08正好叠加在最终结果的第1和2位。
完整代码如下：

class Solution {
public:
    string multiply(string num1, string num2)
    {
        int n1 = num1.size(), n2 = num2.size();
        vector<int> ans(n1 + n2, 0);
        for (int i = n1 – 1; i >= 0; –i) {
            for (int j = n2 – 1; j >= 0; –j) {
                int mul = (num1[i] – ‘0’) * (num2[j] – ‘0’);
                int p1 = i + j, p2 = i + j + 1;
                int sum = mul + ans[p2];
                ans[p1] += sum / 10;
                ans[p2] = sum % 10;
            }
        }
        string ret = "";
        int i = 0;
        while (i < n1 + n2 && ans[i] == 0)
            ++i;
        if (i >= n1 + n2)
            return "0";
        while (i < n1 + n2) {
            ret.push_back(‘0’ + ans[i]);
            ++i;
        }
        return ret;
    }
};

本代码提交AC，用时9MS。

三刷。巧妙方法还是没记住，下面依然是小学生解法，只不过代码好看一点。

class Solution {
public:
	string SingleMultiply(string s, char c) {
		string ans = "";
		int vc = c - '0';
		int carry = 0;
		for (int i = s.size() - 1; i >= 0; --i) {
			int vs = s[i] - '0';
			int prod = vc * vs + carry;
			ans.push_back('0' + (prod % 10));
			carry = prod / 10;
		}
		if (carry > 0)ans.push_back(carry + '0');
		return ans;
	}
	string multiply(string num1, string num2) {
		int n1 = num1.size(), n2 = num2.size();
		if (n1 > n2)return multiply(num2, num1);
		if (num1 == "0")return "0";
		vector<string> prods;
		int max_len = 0;
		for (int i = n1 - 1; i >= 0; --i) {
			string prod = string(n1 - i - 1, '0') + SingleMultiply(num2, num1[i]);
			max_len = prod.size() > max_len ? prod.size() : max_len;
			prods.push_back(prod);
		}
		string ans = "";
		int carry = 0;
		for (int i = 0; i < max_len; ++i) {
			int val = 0;
			for (int j = 0; j < prods.size(); ++j) {
				if (i < prods[j].size())val += (prods[j][i] - '0');
			}
			val += carry;
			ans.push_back('0' + (val % 10));
			carry = val / 10;
		}
		if (carry > 0)ans.push_back('0' + carry);
		reverse(ans.begin(), ans.end());
		return ans;
	}
};

本代码提交AC，用时24MS。