Given two non-negative integersnum1andnum2represented as strings, return the product ofnum1andnum2.

Note:

1. The length of bothnum1andnum2is < 110.
2. Bothnum1andnum2contains only digits0-9.
3. Bothnum1andnum2does not contain any leading zero.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution: 因为数的范围很大，所以整个过程只能用string。把乘和加的逻辑分开

    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        //offset表示补0数
        for (int i = num1.length() - 1, offset = 0; i >= 0; i--, offset++) {
            int cur = num1.charAt(i) - '0';
            if (cur == 0) {
                continue;
            }
            StringBuilder sb2 = new StringBuilder();
            int extra = 0;
            for (int j = num2.length() - 1; j >= 0; j--) {
                int cur2 = num2.charAt(j) - '0';
                int digit = cur * cur2 + extra;
                extra = digit / 10;
                digit %= 10;            
                sb2.append(digit);      
            }
            if (extra > 0) {
                sb2.append(extra);
            }
            add(sb, sb2, offset);
        }
        return sb.reverse().toString();
    }
    private void add(StringBuilder sb, StringBuilder sb2, int offset) {
        if (sb.length() == 0) {
            for (int i = 0; i < offset; i++) {
                sb.append(0);
            }
            sb.append(sb2);
            return;
        } 
        int i = offset, j = 0, extra = 0;
        while (i < sb.length() && j < sb2.length()) {
            int sum = sb.charAt(i) - '0' + sb2.charAt(j) - '0' + extra;
            extra = sum / 10;
            sum %= 10;
            char c = (char)('0' + sum);
            //不能直接sb.setCharAt(i, sum)或char c = '0' + sum
            sb.setCharAt(i, c);
            i++;
            j++;
        }
        while (j < sb2.length()) {
            int sum = sb2.charAt(j) - '0' + extra;
            extra = sum / 10;
            sum %= 10;
            sb.append(sum);
            j++;
        }
        if (extra > 0) {
            sb.append(extra);
        }
    }