Multiply Strings

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.

------------------------- thinking ---------------------------------------
https://leetcode.com/discuss/24502/my-concise-9ms-c-solution
https://leetcode.com/discuss/24503/very-concise-16-ms-c-solution
------------------------- codes ----------------------------------------
   class Solution {
   public:
       string multiply(string num1, string num2) {
           int start1 = 0;
           int start2 = 0;
           int sign1 = 1;
           int sign2 = 1;
           if (num1[0] == '-') {
               sign1 = -1;
               start1 = 1;
           } else if (num1[0] == '+') {
               start1 = 1;
           }
           if (num2[0] == '-') {
               sign2 = -1;
               start2 = 1;
           } else if (num2[0] == '+') {
               start2 = 1;
           }
           while (num1[start1] == '0') {
               start1++;
           }
           while (num2[start2] == '0') {
               start2++;
           }
           string out;
           //bug here -> when one number is 0, all output will be 0
           if (start1 == num1.size() || start2 == num2.size()) {
               return "0";
           }
           //bug here -> the size of out should be (m+n-1) instead of (m+n)
           out.resize(num1.size() - start1 + num2.size() - start2 - 1);
           int carry = 0;
           for (int oid = out.size() - 1; oid >=0; oid--) {
               int cur_out = 0;
               for (int id1 = 0; id1 <= num1.size() - 1; id1++) {
                   int id2 = out.size() - 1 - oid - id1;
                   //bug here-> always pay attention to the valid num of id1 and id2
                   if (id2 >= 0 && id2 <= num2.size() - 1) {
                        int cur1 = num1[num1.size() - 1 - id1] - '0';
                        int cur2 = num2[num2.size() - 1 - id2] - '0';
                        cur_out += cur1 * cur2;
                   }
               }
               cur_out += carry;
               carry = cur_out / 10;
               out[oid] = cur_out % 10 + '0';
           }
           if (carry > 0) {
               char cur = carry + '0';
               string ele(1, cur);
               out = ele + out;
           }
           if (sign1 * sign2 < 0) {
               char cur = '-';
               string ele(1, cur);
               out = ele + out;
           }
           return out;
       }
   };