43. 字符串相乘 - 中等

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

示例 1:

输入: num1 = “2”, num2 = “3” 输出: “6” 示例 2:

输入: num1 = “123”, num2 = “456” 输出: “56088” 说明：

num1 和 num2 的长度小于110。 num1 和 num2 只包含数字 0-9。 num1 和 num2 均不以零开头，除非是数字 0 本身。 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/multiply-strings 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的解

还可优化，用数组代替list，看评论区

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0")  || num2.equals("0")) return "0";
        char[] cs1 = num1.toCharArray();
        char[] cs2 = num2.toCharArray();
        if (cs1.length < cs2.length) {
            char[] cs = cs1;
            cs1 = cs2;
            cs2 = cs;
        }
        LinkedList<LinkedList<Integer>> ls = new LinkedList<>();
        for (int i = cs2.length - 1; i > -1; i--) {
            int carry = 0;
            LinkedList<Integer> lkl = new LinkedList<>();
            for (int j = cs1.length - 1; j > -1; j--) {
                int val = (cs2[i] - '0') * (cs1[j] - '0') + carry;
                int remain = val % 10;
                lkl.addFirst(remain);
                carry = val / 10;
                if (j == 0 && carry != 0) lkl.addFirst(carry);
            }
            ls.addFirst(lkl);
        }
        String result = "";
        LinkedList<Integer> up = ls.removeLast();
        while (!ls.isEmpty()) {
            LinkedList<Integer> nls = new LinkedList<>();
            LinkedList<Integer> down = ls.removeLast();
            result = up.removeLast() + result;
            int carry = 0;
            while (up.size() > 0 || down.size() > 0) {
                int val = (up.isEmpty() ? 0 : up.removeLast()) + (down.isEmpty() ? 0 : down.removeLast()) + carry;
                int remain = val % 10;
                nls.addFirst(remain);
                carry = val / 10;
            }
            if (carry != 0) nls.addFirst(carry);
            up = nls;
        }
        while (!up.isEmpty()){
            result = up.removeLast() + result;
        }
        return result;
    }
}

优解 - 绝

class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")) return "0";
        int m = num1.length(), n = num2.length();

        int [] ansArr = new int[m + n];
        for(int i = m -1; i >= 0; i--){
            int x = num1.charAt(i) - '0';
            for(int j = n -1; j >= 0; j--){
                int y = num2.charAt(j) - '0';
                ansArr[i + j + 1] += x * y;
            }
        }
        for(int i = m + n -1; i > 0; i--){
            ansArr[i -1] += ansArr[i] / 10;
            ansArr[i] = ansArr[i] % 10;
        }
        int index = ansArr[0] == 0 ? 1:0;
        StringBuffer product = new StringBuffer();
        while(index < m+n){
            product.append(ansArr[index]);
            index++;
        }
        return product.toString();

    }
}