Monday, June 30, 2014

Leetcode - 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.


[Thoughts]:
public class Solution {
    public String multiply(String num1, String num2) {
        if(num1.length()==0 || num2.length()==0)
            return "";
        if(num1.equals("0") || num2.equals("0"))
            return "0";
        int len1 = num1.length();
        int len2 = num2.length();
        
        //两个数相乘, 最后得到的乘积的位数最多是两个数的位数之和。 
        int[] temp = new int[len1+len2];
        char[] result = new char[len1+len2];

        for(int i=len1-1; i>=0; i--){
            for(int j=len2-1; j>=0; j--)
                temp[i+j+1] += (num1.charAt(i)-'0') * (num2.charAt(j)-'0');
        }
        
        for(int i=temp.length-1; i>=0; i--){
            if(temp[i]>9)
                temp[i-1] += temp[i]/10;//计算进位
            result[i] = (char)(temp[i]%10 + '0');
        }
        
        String res = new String(result);
        return res.charAt(0)=='0' ? res.substring(1) : res;
    }
}

No comments:

Post a Comment