Labels

Wednesday, March 18, 2015

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.

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
And then, when I was running the program, I found extra corner cases such as,
  • result "00" should be "0"
  • result "0.0" should be "0"
I write two sub functions. One if multiply a string by an integer. The other is plus two String. Because to multiply two strings, I need to multiply a String by one digit each time, and then sum up the results. I also keep a map to record calculated products to speed up the process.

 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