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.
*/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