# 43 Multiply Strings

給兩個string，要將兩者相乘的結果一樣用string形式回傳。

• Idea: 直覺就是想follow 一般乘法規則。依序讀兩個字串，把乘法結果存到int ans裡面。但問題是int的範圍不夠大，數字超過int範圍的input就存不了。 那可以改一下儲存結果的container，String有點難操作，int array是不錯的選擇。

• Code: 用ans來存就不用keep carry，而且不同被乘數位數的結果可以直接存在ans裡面。更新ans的規則需要注意。然後最後要特別處理00和0的case。

  public class Solution {
    public String multiply(String num1, String num2) {
        /*
        follow the rule of multiplication, save result in int[] ans
        last, put ans[] into a string
        */
        int m = num1.length();
        int n = num2.length();
        int[] ans = new int[m+n];
  
        for(int i=m-1; i>=0; i--){
            for(int j=n-1; j>=0; j--){
                int i1 = num1.charAt(i)-'0';
                int i2 = num2.charAt(j)-'0';
                int pos = i+j;
                int cur = i1*i2 + ans[pos+1];
  
                ans[pos+1] = cur % 10;
                ans[pos] += cur/10;
            }
        }
  
        String s = "";
        for(int i=0; i<ans.length; i++){
            //System.out.print(ans[i]+" ");
            if(!(s.length() == 0 && ans[i] == 0))
                s += ans[i];
        }
        return s.length() == 0 ? "0" : s;
    }
  }