Note: The numbers can be arbitrarily large and are non-negative.
Naive Way: The algorithm for this problem should be simple, which is direct multiplication. However, multiply string will have a lot of corner cases. List all corner cases that I can think of.
- -/+ at the front
- "." fraction number in the middle
- extra zeros at tail
- result "00" should be "0"
- result "0.0" should be "0"
public class Solution {
public String multiply(String num1, String num2) {
String rslt = "0";
Map<Integer, String> map = new HashMap<Integer, String>();
// Eliminate "." for num1 and num2, put them into new String. Get "." position. Get -/+
int pointPosition = 0;
boolean negative = false;
StringBuilder n1 = new StringBuilder();
StringBuilder n2 = new StringBuilder();
for(int i = 0;i < num1.length();i++)
if(num1.charAt(i)=='.') pointPosition+= num1.length()-1-i;
else if(num1.charAt(i) =='-') negative = !negative;
else if(num1.charAt(i)!='+') n1.append(num1.charAt(i));
for(int j = 0;j < num2.length();j++)
if(num2.charAt(j)=='.') pointPosition+= num2.length()-1-j;
else if(num2.charAt(j) =='-') negative = !negative;
else if(num2.charAt(j)!='+') n2.append(num2.charAt(j));
// multiply one digit each time
for(int j = n2.length()-1;j >= 0;j--){
int digit = (int)(n2.charAt(j)-'0');
if(digit!=0){
String product;
if(map.containsKey(digit))
product = map.get(digit);
else
product = multiply(n1.toString(), digit);
map.put(digit, product);
if(!product.equals("0"))
for(int u = 0;u < n2.length()-1-j;u++) product += "0";
rslt = plus(rslt, product);
}
}
// add "."
if(pointPosition > rslt.length()-1)
for(int u = 0;u < pointPosition - (rslt.length()-1);u++)
rslt = "0" + rslt;
if(pointPosition!=0)
rslt = rslt.substring(0, rslt.length()-pointPosition) + "." + rslt.substring(rslt.length()-pointPosition, rslt.length());
// get rid of tail zeros when it's fraction number
if(pointPosition!=0)
while(rslt.length() > 1 && (rslt.charAt(rslt.length()-1) == '0' || rslt.charAt(rslt.length()-1) == '.'))
rslt = rslt.substring(0, rslt.length()-1);
// add sign
if(negative) rslt = "-"+rslt;
return rslt;
}
public String multiply(String num1, int num2){
int i = num1.length();
int carry = 0;
StringBuilder str = new StringBuilder();
while(--i >= 0){
int product = (int)(num1.charAt(i)-'0') * num2 + carry;
int remain = product%10;
carry = product/10;
str.append((char)('0'+remain));
}
if(carry!=0) str.append((char)('0'+carry));
return str.reverse().toString();
}
public String plus(String num1, String num2) {
int carry = 0;
StringBuilder rslt = new StringBuilder();
int i = num1.length()-1, j = num2.length()-1;
while(i >= 0 && j >= 0){
int value = (int)(num1.charAt(i)-'0') + (int)(num2.charAt(j)-'0') + carry;
carry = value/10;
value = value%10;
rslt.append((char)(value+'0'));
i--;
j--;
}
while(i >= 0){
int value = (int)(num1.charAt(i)-'0') + carry;
carry = value/10;
value = value%10;
rslt.append((char)(value+'0'));
i--;
}
while(j >= 0){
int value = (int)(num2.charAt(j)-'0') + carry;
carry = value/10;
value = value%10;
rslt.append((char)(value+'0'));
j--;
}
if(carry!=0) rslt.append((char)(carry+'0'));
return rslt.reverse().toString();
}
}
No comments:
Post a Comment