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.

这道题挺巧妙的,首先为了不溢出,我们就像小学乘法一样一位一位算,index因为从最后一位开始,所以我们先把两个string都reverse一下,这样index更方便

然后是carry的处理,我们先用一个整数数组将所有的积的加法结果存下来,不管carry,然后再遍历这个数组将需要进位的进位,注意length m和n的数相乘结果不可能超过m+n位。最后一位是没有进位的。

最后就是要把结果reverse回来,注意开头的0要删掉

public class Solution {
    public String multiply(String num1, String num2) {
       
        int [] result = new int [num1.length() + num2.length()];
        char [] r = new char [result.length];
        StringBuilder num1R = new StringBuilder(num1).reverse();
        StringBuilder num2R = new StringBuilder(num2).reverse();
        //calculate bit by bit
        for (int i = 0; i < num1R.length(); i++) {
            for (int j = 0; j < num2R.length(); j++) {
                result[i+j] += (num1R.charAt(i) - '0') * (num2R.charAt(j) - '0');
            }
        }
        
        for (int i = 0; i < result.length; i++) {
            int d = result[i]%10;
            int c = result[i]/10;
            //result[i] = d;
            r[i] = (char)(d + '0');
            if (i < result.length - 1) // not the last digit, last digit will have no carry
                result[i+1] += c;
        }
        
        StringBuilder f = new StringBuilder(new String(r));
        //remove heading 0s
        while(f.length() != 1) {
            if (f.charAt(f.length() - 1) != '0')
                break;
            f.deleteCharAt(f.length() - 1);
        }
        
        f.reverse();
        
        return new String(f);
    }
}

Second Submission:

Using the same method, but defined a separate method to add two (reversed) string numbers (with different length)

public class Solution {
    public String multiply(String num1, String num2) {
        String r1 = reverse(num1);
        String r2 = reverse(num2);
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < r1.length(); i++) {
            int carry = 0;
            StringBuilder num = new StringBuilder();
            for (int j = 0; j < r2.length(); j++) {
                int n1 = (r1.charAt(i) - '0');
                int n2 = (r2.charAt(j) - '0');
                int tmp = n1*n2 + carry;
                num.append(tmp%10);
                carry = tmp/10;
            }
            num.append(carry);
            for (int k = 0; k < i; k++) {
                num.insert(0, '0');
            }
            result = reversedAdd(num, result);
        }
        //remove heading 0s
        while(result.length() > 1) {
            if (result.charAt(result.length() - 1) == '0') {
                result.deleteCharAt(result.length() - 1);
            }
            else {
                break;
            }
        }
        return reverse(new String(result));
    }
    
    public String reverse(String s) {
        return new String(new StringBuilder(s).reverse());
    }
    
    public StringBuilder reversedAdd(StringBuilder s1, StringBuilder s2) {
        StringBuilder result = new StringBuilder();
        StringBuilder op1= new StringBuilder();
        StringBuilder op2 = new StringBuilder();
        if (s1.length() < s2.length()) {
            op1 = s1;
            op2 = s2;
        }
        else {
            op1 = s2;
            op2 = s1;
        }
        // op1.length <= op2.length
        int carry = 0;
        for(int i = 0; i < op2.length(); i++) {
            int sum = 0;
            if (i < op1.length())
                sum = (int)(op1.charAt(i) - '0') + (int)(op2.charAt(i) - '0') + carry;
            else 
                sum = (int)(op2.charAt(i) - '0') + carry;
            carry = sum/10;
            sum = sum%10;
            result.append(Character.forDigit(sum, 10));
        }
        if (carry > 0)
            result.append(Character.forDigit(carry, 10));
        return result;
    }
}

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