Leetcode --- Multiply Strings(Medium)
===

## Description

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

**Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.**

Input給兩個字串把它當成數字輸出兩數相乘,且不能直接轉乘數字相乘或用BigInteger(比long還大的integer),==i.e 如果直接乘會Overflow==.

### Examples

* Ex1:
**Input:** num1 = "2", num2 = "3"
**Output:** "6"

* Ex2:
**Input:** num1 = "123", num2 = "456"
**Output:** "56088"

### Constrains
* 1 <= num1.length, num2.length <= 200
* num1 and num2 consist of digits only.
* Both num1 and num2 do not contain any leading zero, except the number 0 itself.

## Solution:

* 解最多有多少個數字 ?
=> 設4位數 * 4位數 = 最多 8 位數
=> ==ans.length <= num1.length + num2.length==

* 如何算出解?
=>設4位數 1234 * 9876

                 input [3]    [2]    [1]   [0]
                        1      2      3     4
                     *  9      8      7     6
                      --------------------------
                        6     12     18    24
                   7   14     21     28
              8   16   24     32 
        + 9  18   27   36
        -----------------------------------------
          9  26   50  130     65     46     24
    >進位
ans  [7] [6] [5]  [4]  [3]    [2]    [1]    [0]
    ----------------------------------------------
    > 1   2   1    8    6      9      8      4  

=>可從中間看出將==計算中每個一小部分的解==**丟到**==對的ans bucket中==再相加考慮進位就可以得解

=>可發現:
* num1[0] * num2[0] = ans[0]
* num1[2] * num2[3] = ans[5]
==> **ans[i+j]** (對的bucket)= **num1[i] + num2[j]** (小部分解)==

import java.util.*;
class Solution {
    public String multiply(String num1, String num2) {
        int[] ans = new int[num1.length()+ num2.length()];
        
        num1 = new StringBuilder(num1).reverse().toString();
        num2 = new StringBuilder(num2).reverse().toString();
         
        int[] num1Int = new int[num1.length()];
        int[] num2Int = new int[num2.length()];
        
        for(int i =0;i<num1.length();i++)
            num1Int[i] = num1.charAt(i) -'0'; //return '1~9'(character) and minus '0' in ASCII
        for(int i =0;i<num2.length();i++)
            num2Int[i] = num2.charAt(i) -'0';
        
        for(int i =0;i<num1.length();i++)
            for(int j =0;j<num2.length();j++)
                ans[i+j] += num1Int[i] * num2Int[j];
            
        for(int i =0 ;i<ans.length-1;i++)
        {
            ans[i+1] += ans[i]/10;
            ans[i] %=10;
        }
        
        StringBuilder sb = new StringBuilder(Arrays.toString(ans));
        
        sb.deleteCharAt(0);
        sb.deleteCharAt(sb.length()-1);
        
        while(sb.indexOf(",") != -1) 
        {
            int com = sb.indexOf(",");
              sb.deleteCharAt(com);
        }
        while(sb.indexOf(" ") != -1)
        { 
             int space = sb.indexOf(" ");
             sb.deleteCharAt(space);
        }
        sb.reverse();
        
        while(sb.charAt(0) == '0' && sb.length() >1)
            sb.deleteCharAt(0);
      
        return sb.toString();
    }
}

line 4: 解的最大長度為兩個input長度相加
line 6.7:做reverse之後Array順序會比較好操作
line 12~15:將String(input)轉為int array,charAt原型如下

String.charAt:
public String charAt(int index)
...

再減去'0',將ASCII轉成純數字.

line 17~19:小部分解丟到對的bucket
line 21~25:進位
line 27:以下全部都是再將int array轉回String
由於Arrays.toString(int[])輸出結果大致長這樣
[3 ,5 ,8 ,9 ,4],所以line27~40都在解決這個問題
line 44:要考慮最前面不可為0

### Complexity Analysis

要跑過兩個input長度
=> ==O(n*m)==

### Submission on Leetcode

Runtime: **6 ms**, faster than **36.63%** of Java online submissions for Multiply Strings.
Memory Usage: **39.3 MB**, less than **19.46%** of Java online submissions for Multiply Strings.

## Reference

=>[Multiply Strings leetcode java by 愛做飯的小瑩子](https://iter01.com/65947.html)

class Solution {
    public String multiply(String num1, String num2){
    num1 = new StringBuilder(num1).reverse().toString();
     num2 = new StringBuilder(num2).reverse().toString();
     // even 99 * 99 is < 10000, so maximaly 4 digits
     int[] d = new int[num1.length() + num2.length()];
     for (int i = 0; i < num1.length(); i++) {
         int a = num1.charAt(i) - '0';
         for (int j = 0; j < num2.length(); j++) {
             int b = num2.charAt(j) - '0';
             d[i + j] += a * b;
         }
     }
     StringBuilder sb = new StringBuilder();
     for (int i = 0; i < d.length; i++) {
         int digit = d[i] % 10;
         int carry = d[i] / 10;
         sb.insert(0, digit);
         if (i < d.length - 1)
             d[i + 1] += carry;
         }
     //trim starting zeros
     while (sb.length() > 0 && sb.charAt(0) == '0') {
         sb.deleteCharAt(0);
     }
     return sb.length() == 0 ? "0" : sb.toString();
}
}

###### tags: `Leetcode` `Medium` `String`