This question should be quite easy. Just divide numbers multiplication into 2 steps: 1) multiplication of one digit and one number, 2) sum up results from step 1.
Time complexity should be O(n^2). I am not sure whether there exits better algorithm. If you know one, please let me know. Thanks.
public class Solution {
public String multiply(String num1, String num2) {
if(num1.equals("0") || num2.equals("0")) return "0";
StringBuffer res = new StringBuffer();
String prePrdct = null;
String crntPrdct = null;
for(int i = num1.length() - 1; i >= 0; i--){
crntPrdct = multiply(num2, num1.charAt(i),num1.length() - 1 - i);
prePrdct = add(crntPrdct,prePrdct);
}
return prePrdct;
}
public String multiply(String num1, char num2,int numZeros){
StringBuffer res = new StringBuffer();
int get = 0;
for(int i = num1.length() - 1; i >= 0 ; i--){
int prdct = (num1.charAt(i) - '0') * (num2 - '0') + get;
get = prdct/10;
res.append(prdct%10);
}
if(get != 0) res.append(get);
res = res.reverse();
for(int i = 0; i < numZeros;i++){
res.append(0);
}
return res.toString();
}
public String add(String num1, String num2){
if(num2 == null) return num1;
StringBuffer res = new StringBuffer();
if(num1.length() > num2.length()){
int i = num1.length() - 1;
int j = num2.length() - 1;
int get = 0;
for(; j >= 0; ){
int sum = (num1.charAt(i) - '0') + (num2.charAt(j) - '0') + get;
get = sum / 10;
res.insert(0,sum%10);
i --;
j --;
}
for(;i>=0;i--){
int sum = (num1.charAt(i) - '0') + get;
get = sum/10;
res.insert(0,sum%10);
}
if(get!=0) res.insert(0,get);
}
else{
int i = num1.length() - 1;
int j = num2.length() - 1;
int get = 0;
for(; i >= 0; ){
int sum = (num1.charAt(i) - '0') + (num2.charAt(j) - '0') + get;
get = sum / 10;
res.insert(0,sum%10);
i --;
j --;
}
for(;j>=0;j--){
int sum = (num2.charAt(j) - '0') + get;
get = sum/10;
res.insert(0,sum%10);
}
if(get!=0) res.insert(0,get);
}
return res.toString();
}
}
Hello, welcome to Yizhe's Blog. I am Yizhe Liu, graduated from University of Arizona, with Master degree, major in Electrical and Computer Engineering. Actually, I am software guy. In my blog, many posts are about the Leetcode questions. I will post my ideas and implementations, which are accepted by Leetcode. If you have different opinions, please leave comment. I am happy to discuss with you. So lets start rocking them!!!
No comments:
Post a Comment