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.

  class 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;
    }
  };
  

  Notes
• 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);