Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Analysis

• 建一个数组用来存每一位的数
• 把每一位相乘放到对应的数组位置
• 把大于10的位置进位
• 把数组转化为string

Code

public class Solution {
    public String multiply(String num1, String num2) {
        int n1=num1.length(), n2=num2.length();
        //注意这里建的数组长度为n1+n2，实际上用的到的长度只有n1+n2-1，多加一位的目的是最后一位有可能进位，所以这样比较方便。改变数组长度非常麻烦，要重新copy数组。
        int[] products = new int[n1+n2];
        //循环从string的末尾向前，符合乘法运算的规则
        for(int i=n1-1; i>=0; i--){
            for(int j=n2-1; j>=0; j--){
                int d1 = num1.charAt(i)-'0';
                int d2 = num2.charAt(j)-'0';
                products[i+j+1] += d1*d2;
            }
        }

        //完成进位
        int carry=0;
        for (int i=n1+n2-1; i>=0; i--){
            int tmp = carry+products[i];
            carry = tmp/10;
            products[i] = tmp%10;
        }

        StringBuilder sb = new StringBuilder();
        for (int num:products) sb.append(num);
        while(sb.length()!=0 && sb.charAt(0)=='0') sb.deleteCharAt(0);
        return sb.length()==0 ? "0":sb.toString();

    }
}

Note

• 数字char转为int的标准写法：string.charAt(i)-'0'
• stringBuilder.deleteCharAt(i)
• stringBuilder.toString()

Reference

Leetcode