LeetCode043——字符串相乘

原题链接：https://leetcode-cn.com/problems/multiply-strings/description/

题目描述：

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"

输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"

输出: "56088"

思路：

本题的思路很简单，就是单纯地模拟手工算法得出结果，但想把这个程序写得优美还是有难度的，下面将罗列我自己写程序时的一个个不同的实现版本。

逻辑如下：

（1）数组stringBuilders里存储的是字符串num2中的各位上的数和num1相乘的结果，比如对于123 * 456而言，其存储的就是738，615，492。

（2）给数组stringBuilders中的元素添0，使其成为738，6150，49200。

（3）反转stringBuilders中的元素，使其成为837，0516，00294。

（4）对stringBuilders中的元素进行相加操作，使其成为88065。

（5）反转（4）中的结果，得到最终答案56088。

注意，在程序开始时，需要对乘数为0的情况做特殊处理，否则会出现类似0000的答案。

时间复杂度是O(n1 * n2)，其中n1为字符串num1的长度，n2为字符串num2的长度。实现过程中使用了一个长度为n2的StringBuilder类型的数组，而数组中每个元素的长度是n1或者n1 + 1，因此空间复杂度为O(n1 * n2)。

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

        if ((n1 == 1) && (Integer.parseInt(num1) == 0)) {
            return num1;
        }

        if ((n2 == 1) && (Integer.parseInt(num2) == 0)) {
            return num2;
        }

        StringBuilder result = new StringBuilder();
        StringBuilder[] stringBuilders = new StringBuilder[n2];

        for (int i = n2 - 1; i >= 0; i--) {
            StringBuilder stringBuilder = new StringBuilder();
            int flag = 0;

            for (int j = n1 - 1; j >= 0; j--) {
                Integer integer = Integer.parseInt(num1.substring(j, j + 1)) * Integer.parseInt(num2.substring(
                            i, i + 1));
                stringBuilder.append((integer + flag) % 10);
                flag = (integer + flag) / 10;
            }

            if (flag > 0) {
                stringBuilder.append(flag);
            }

            stringBuilders[n2 - i - 1] = stringBuilder.reverse();
        }

        for (int i = 0; i < n2; i++) {
            for (int j = 0; j < i; j++) {
                stringBuilders[i].append(0);
            }
        }

        for (int i = 0; i < n2; i++) {
            stringBuilders[i] = stringBuilders[i].reverse();
        }

        int flag = 0;
        int maxLen = 0;

        for (int i = 0; i < n2; i++) {
            maxLen = Math.max(maxLen, stringBuilders[i].length());
        }

        for (int i = 0; i < maxLen; i++) {
            int sum = 0;

            for (int j = 0; j < n2; j++) {
                if (i < stringBuilders[j].length()) {
                    sum += Integer.parseInt(stringBuilders[j].substring(i, i +
                            1));
                }
            }

            int num = (sum + flag) % 10;
            flag = (sum + flag) / 10;
            result.append(num);
        }

        if (flag > 0) {
            result.append(flag);
        }

        return result.reverse().toString();
    }
}