Sunday, February 9, 2014

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.

Solution:
first try: StringArray--> complicated 
second try: int array


public class Solution {
    public String multiply(String num1, String num2) {
        int len1 = num1.length(), len2 = num2.length(), len = len1 + len2;
        int[] ret = new int[len];
        for(int i = len1 - 1; i >= 0; i--){
            for(int j = len2 - 1; j >= 0; j--){
                int x = num1.charAt(i) - '0';
                int y = num2.charAt(j) - '0';
                int offset = (len1-1-i) + (len2-1-j);
                int tmp = x * y + ret[offset];
                ret[offset] = tmp % 10;
                ret[offset+1] += tmp / 10; 
            }
        }
        int j = len - 1;
        while(j > 0 && ret[j] == 0) j--;
        StringBuilder str = new StringBuilder();
        for(int i = j; i >= 0; i--) str.append(ret[i]);
        return str.toString();
    }
}

No comments:

Post a Comment