# 【LeetCode】 43. Multiply Strings

## 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:
> - The length of both num1 and num2 is < 110.
> - Both num1 and num2 contain only digits 0-9.
> - Both num1 and num2 do not contain any leading zero, except the number 0 itself.
> - You must not use any built-in BigInteger library or convert the inputs to integer directly.

> 給兩個字串num1和num2代表兩個非負整數，回傳num1和num2的乘積，回傳型態同樣使用字串。
> 注意：
> - num1和num2的長度小於110。
> - num1和num2都只會包含數字0-9。
> - num1和num2都不會有0在開頭，除非他們本身就等於零。
> - 你不應該使用任何內建大數函式庫，或是直接轉換輸入型別到數字。

## Example:

Example 1:

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


Example 2:

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

## Solution

* **大數運算**的題目，基本上就你要你實作大數乘法。
* 將每一個位元都去表示一位數，計算時先不考慮進位(數字可以大於10)，等到每一位元都加總完之後，再由最低位元往上進位。
* 需要注意的點：
* 用`string`相當於`vector<char>`，你可能會因此溢位。
* 注意高位元和低位元，運算時不要搞反了。
* 多餘的零必須移除。

### Code

class Solution {
public:
    string multiply(string num1, string num2) {
        int s1=num1.size(),s2=num2.size();
        vector<short> mul(s1+s2,0);
        
        //compute each bit
        for(int i=0;i<s1;i++)
        {
            for(int j=0;j<s2;j++)
            {
                mul[s1+s2-2-(i+j)]+=(num1[i]-'0')*(num2[j]-'0');
            }
        }
        
        //compute carry from low bit to high bit
        for(int i=0;i<mul.size();i++)
        {
            while(mul[i]>9)
            {
                mul[i+1]++;
                mul[i]-=10;
            }
            mul[i]+='0';
        }
        
        //reverse and erase 0
        string ans;
        bool isFirst=true;
        for(int i=mul.size()-1;i>=0;i--)
        {
            if(mul[i]=='0')
            {
                if(!isFirst)
                    ans.push_back(mul[i]);
            }
            else
            {
                isFirst=false;
                ans.push_back(mul[i]);
            }
        }
        //if equal 0
        if(isFirst) return "0";
        
        return ans;
    }
};

###### tags: `LeetCode` `C++`