[刷题防痴呆] 0043 - 字符串相乘 (Multiply S

题目地址

https://leetcode.com/problems/multiply-strings/description/

题目描述

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"

思路

• 模拟两数相乘.
• 两数相乘得到的乘积的长度其实其实不会超过两个数字的长度之和, 若 num1 长度为m, num2 长度为n，则 num1 * num2 的长度不会超过 m+n.
• num1 和 num2 中任意位置的两个数字相乘, 得到的两位数在最终结果中的位置是确定的, 比如 num1 中位置为i的数字乘以 num2 中位置为j的数字, 那么得到的两位数字的位置为 i+j 和 i+j+1.

关键点

• 从后往前计算.
• 前面的0需要删掉. 然后每一位加入到StringBuffer中.
• 如果最后StringBuffer还是空, 则return "0".

代码

• 语言支持：Java

class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();

        int[] arr = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int product = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j;
                int p2 = i + j + 1;
                int sum = arr[p2] + product;
                arr[p1] += sum / 10;
                arr[p2] = sum % 10;
            }
        }

        StringBuffer sb = new StringBuffer();
        int index = 0;
        while (index < arr.length && arr[index] == 0) {
            index++;
        }
        while (index < arr.length) {
            sb.append(arr[index]);
            index++;
        }
        if (sb.length() == 0) {
            return "0";
        }
        return sb.toString();
    }
}