【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++