43. Multiply Strings

Problem from leetcode 43. Multiply Strings

---

这道题属于大整数的算术(big integer)，对于这种题我们只需要模拟在纸上做的时候的process就行了。

---

class Solution {
public:
    string multiply(string num1, string num2) {
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int len1 = num1.size(), len2 = num2.size();
        vector<int> temp(len1+len2, 0);
        for(int i = 0; i < len1; ++i)
            for(int j = 0; j < len2; ++j)
                temp[i+j] += (num1[i]-'0')*(num2[j]-'0');
        string result(len1+len2, '0');
        int carry = 0;
        for(int i = 0; i < len1+len2-1; ++i) 
        { 
            result[i] = (temp[i]+carry)%10 + '0'; 
            carry = (temp[i]+carry)/10; 
        } 
        if(carry > 0)//carry must less then 10
            result[len1+len2-1] = carry+'0';
        else
            result.pop_back();
        int size = result.size();
        //be careful "921" multiply "0" should be "0"
        //and "0" multiply "0" should be "0"
        while(result[size-1] == '0' && size-1!=0)
        {
            result.pop_back();
            --size;
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

Java:

public class Solution {
    public String multiply(String num1, String num2) {
        num1 = new StringBuilder(num1).reverse().toString();
        num2 = new StringBuilder(num2).reverse().toString();
        int len1 = num1.length(), len2 = num2.length();
        int[] temp = new int[len1+len2];
        for(int i = 0; i < len1+len2; ++i) 
            temp[i] = 0;
        for(int i = 0; i < len1; ++i)
            for(int j = 0; j < len2; ++j)
                temp[i+j] += (num1.charAt(i)-'0')*(num2.charAt(j)-'0');
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        for(int i = 0; i < len1+len2-1; ++i)
        {
            //not append (carry+temp[i])%10+'0'
            sb.append((carry+temp[i])%10);
            carry = (carry+temp[i])/10;
        }
        if(carry != 0)
            sb.append(carry);
        int index = sb.length()-1;
        while(sb.charAt(index) == '0' && index!= 0)
            --index;
        sb.delete(index+1, sb.length());
        return sb.reverse().toString();
    }
}