43 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.
- Converting the input string to integer is NOT allowed.
- You should NOT use internal library such as BigInteger.
Notesclass Solution { public: string multiply1(string num, string d) { int n = num.size(), add = 0; string res; for ( int i = 0; i <= n-1; i++ ) { int n1 = stoi(num.substr(i, 1)), n2 = stoi(d); res += to_string((n1*n2 + add)%10); add = (n1*n2+add)/10; } if ( add != 0 ) res += to_string(add); return res; } string add(string num1, string num2) { int n1 = num1.size(), n2 = num2.size(); string res; int v1, v2, add = 0; for ( int i = 0; i <= max(n1, n2)-1; i++ ){ if ( i >= n1 ) v1 = 0; else v1 = stoi(num1.substr(i, 1)); if ( i >= n2 ) v2 = 0; else v2 = stoi(num2.substr(i, 1)); res += to_string(( v1 + v2 + add )%10); add = ( v1 + v2 + add )/10; } if ( add != 0 ) res += to_string(add); return res; } string multiply(string num1, string num2) { int n1 = num1.size(), n2 = num2.size(); if ( n1 == 0 or n2 == 0 ) return "0"; if ( num1 == "0" or num2 == "0" ) return "0"; reverse(num1.begin(), num1.end()); reverse(num2.begin(), num2.end()); string zero = "", res = ""; for ( int i = 0; i <= n2-1; i++ ) { string tmp = zero + multiply1(num1, num2.substr(i, 1)); res = add(res, tmp); zero += "0"; } reverse(res.begin(), res.end()); return res; } };
- Reversing string helps to simplify the multiplication.
- Using multiply1 to treat multiplication with single-digit number.
- Using add to get the sum of every multiply1 result. Note the trick to putting "zeros" as the prefix.
example: "14" * "15" -- convert to "41" * "51" -- multiply1("41", "5") = "07" -- add("", "07") = "07" -- multiply1("41", "1") = "41" -- add("07", "041") = "012" -- reverse to "210"
string to integer:
stoi(string s);