Saturday, March 2, 2013

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.
*/
class Solution {
public:
    vector<int> convertToDigit(string num){
        int size = num.length();
        char init = '0';
        vector<int> result;
        int digit;
        for(int i=0; i<size; i++){
            digit = num[i] - init;
            if(digit>9 || digit<0){
                result.clear();
                return result;
            }
            result.push_back(digit);
        }
        return result;
    }
    char convertToChar(int num){
       char init = '0';
       return init+num;
    }
  
    string multiply(string num1, string num2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> left;
        vector<int> right;
        string result;
      
        left = convertToDigit(num1);
        right = convertToDigit(num2);
      
        vector<vector<int>> temp;
        vector<int> line;
        int i, j, k;
        int multi = 0;
        int higher = 0;
        for(i=0; i<right.size(); i++){
            line.clear();
            higher = 0;
            for(j=left.size()-1; j>=0; j--){
                multi = right[i]*left[j];
                line.insert(line.begin(), multi%10 + higher);
                higher = multi/10;
            }
            if(higher>0) line.insert(line.begin(), higher);
            else line.insert(line.begin(), 0);
            temp.push_back(line);
        }
      
        int sum;
        int plus = 0;
        int colSize = right.size();
        int rowSize = left.size()+1;
        for(k=colSize+rowSize-2; k>=0; k--){
            sum = 0;
            for(i=colSize-1; i>=0; i--){
              for(j=rowSize-1; j>=0; j--){
                if(i+j==k){
                   sum = sum + temp[i][j];
                   }
               }
            }
            sum = sum + plus;
            result.insert(0, 1, convertToChar(sum%10));
            plus = sum/10;
        }
       
        i=0;
        while(result[i]=='0'){
         i++;
        }
        if(i==result.size()) i = i-1;
       
        string substring = result.substr(i);
       
        return substring;
    }
};

No comments:

Post a Comment