Leetcode–Multiply Strings

The Problem:

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.

Notes:

  1. The problem can be broken down to String add and String multiply by char. Multiply the first string by each character in second string from right to left, and add the result of each step.
  2. Special condition: if either input is zero then return zero, otherwise the result from multiplication would be a series of zeros.
  3. If the total number of digits of input number is less than 9, means the result can fit in a normal integer, can take them as int and do multiply.

Java Solution:

public class Solution {
    public String multiply(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        
        if(len1 + len2 < 9){
            int res = Integer.parseInt(num1) * Integer.parseInt(num2);
            return String.valueOf(res);
        }
        if(num1.equals("0") || num2.equals("0"))return "0";
        String res = "0";
        for(int i = 0; i < len2; i++){
            String mult = multByChar(num1, num2.charAt(len2-1-i));
            int k = i;
            while(k>0){
                k--;
                mult = mult+"0";
            }
            res = addStr(mult, res);
        }
        return res;
    }
    
    private String addStr(String a, String b){
        int lena = a.length();
        int lenb = b.length();
        int len = Math.max(lena, lenb)+1;
        char[] res = new char[len];
        int carry = 0;
        int i;
        for(i = 1; i <= Math.min(lena, lenb); i++){
            int sum = (a.charAt(lena-i)-'0') + (b.charAt(lenb-i)-'0')+carry;
            res[len-i] = (char)(sum%10+'0');
            carry = sum/10;
        }
        while(i<=lena){
            int sum = (a.charAt(lena-i)-'0')+carry;
            res[len-i] = (char)(sum%10+'0');
            carry = sum/10;
            i++;
        }
        while(i<=lenb){
            int sum = (b.charAt(lenb-i)-'0')+carry;
            res[len-i] = (char)(sum%10+'0');
            carry = sum/10;
            i++;
        }
        if(carry==0){
            return new String(res).substring(1);
        }
        else{
            res[0] = (char)(carry+'0');
            return new String(res);
        }
    }
    
    private String multByChar(String num, char ch){
        if(ch=='0') return "0";
        int len = num.length();
        char[] res = new char[len+1];
        int carry = 0;
        int mul = ch-'0';
        for(int i = 0; i < len; i++){
            int pro = mul * (num.charAt(len-1-i)-'0') + carry;
            res[len-i] = (char)(pro%10+'0');
            carry = pro/10;
        }
        if(carry == 0){
            return new String(res).substring(1);
        }
        else{
            res[0] =(char)(carry+'0');
            return new String(res);
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s