LeetCode Q43: Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Solution is trivial , multiple each digit of num2 to num1 and add all results up. Be careful of carries. Also a trick used here to speed up the code a little bit is to pre allocate the space for resulting number. The length of resulting number is no longer than num1.length()+num2.length(). Then the multiplication result of num1[i] and num2[j] should be put in result[i+j].

	class Solution {
	public:
	string multiply(string num1, string num2) {
	if(num1==string("0")||num2==string("0"))
	return string("0");
	unsigned int l1=num1.size(),l2=num2.size();
	if (l1==0||l2==0) return "0";
	vector<int> v(l1+l2,0);
	for (unsigned int i=0;i<l1;i++){
	int carry=0;
	int n1=(int)(num1[l1-i-1]-'0');//Calculate from rightmost to left
	for (unsigned int j=0;j<l2;j++){
	int n2=(num2[l2-j-1]-'0');//Calculate from rightmost to left
	int sum=n1*n2+v[i+j]+carry;
	carry=sum/10;
	v[i+j]=sum%10;
	}
	if (carry>0)
	v[i+l2]+=carry;
	}
	int start=l1+l2-1;
	while(v[start]==0) start--;
	if (start==-1) return "0";
	string s="";
	for (int i=start;i>=0;i--)
	s+=(char)(v[i]+'0');
	return s;
	}
	};

view raw Q43MultipleString.cpp hosted with ❤ by GitHub