LeetCode [43] Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

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

Example 2:

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

Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contain only digits 0-9.
3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class Solution { public: string multiply(string num1, string num2) { int n1 = num1.size(), n2 = num2.size(); if(n1<n2) return multiply(num2, num1); string ret(n1+n2, '0'); int carryon = 0, res = 0, pos; for(int i2 = n2-1; i2>=0; --i2) { int v2 = num2[i2]-'0'; for(int i1 = n1-1; i1>=0; --i1) { int v1 = num1[i1]-'0'; pos = i1+i2+1; int r = v1*v2+carryon+(ret[pos]-'0'); ret[pos] = char(r%10+'0'); carryon = r/10; } if(carryon>0) { ret[pos-1] = char(carryon+'0'); carryon = 0; } } if(carryon>0) { ret[pos-1] = char(carryon+'0'); } int p = ret.find_first_not_of('0'); if(p<0) return "0"; return ret.substr(p, ret.size()-p); } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

class Solution { public String multiply(String num1, String num2) { if(num1.length() < num2.length()){ return multiply(num2, num1); } StringBuilder ret = new StringBuilder(); for(int i=num2.length()-1; i>=0; --i){ ret = add(ret, multiply1(num1, num2.charAt(i), num2.length()-1-i)); } int i=0; while(i<ret.length()-1 && ret.charAt(i)=='0') i++; return ret.substring(i); } StringBuilder add(StringBuilder num1, StringBuilder num2){ StringBuilder ret = new StringBuilder(); num1.reverse(); num2.reverse(); int i = 0, j = 0, c = 0; while(i<num1.length() || j<num2.length()){ if(i<num1.length()) c += num1.charAt(i++) - '0'; if(j<num2.length()) c += num2.charAt(j++) - '0'; ret.append(c%10); c = c/10; } if(c>0){ ret.append(c); } return ret.reverse(); } StringBuilder multiply1(String a, char b, int offset){ StringBuilder sb = new StringBuilder(); int c = 0; for(int i=a.length()-1; i>=0; --i){ c += (a.charAt(i) - '0')*(b-'0'); sb.append(c%10); c = c/10; } if(c!=0){ sb.append(c); } sb.reverse(); for(int i=0; i<offset; ++i){ sb.append(0); } return sb; } }