2014年5月11日星期日

Loop Solution - Multiply Strings

The idea is to use a int array which size is sum of two Strings, to process multiplication.

Index would be i + j, update the cell each iteration by new+old, notice that start from the end of the String, watch the index from last to first. Remember the carry, which should be n+o/10 and i+j value would be n + o%10. Carry index would be i + s2.length().

Clean 0 except if last digit so use i > 0 without equal. then load all remaining with the index i > 0 after cleaning to result and return.

public class Solution {
    public String multiply(String num1, String num2) {
       
        int[] process = new int[num1.length() + num2.length()];
        for(int i = 0; i < num1.length(); i++){
            int cur1 = num1.charAt(num1.length() - 1 - i) - '0';
            int carry = 0;
            for(int j = 0; j < num2.length(); j++){
                int cur2 = num2.charAt(num2.length() - 1 -j) - '0';
                process[i + j] += cur1 * cur2 + carry;
                carry = process[i + j] / 10;
                process[i + j] %= 10;
            }
            process[i + num2.length()] += carry;
        }
       
        //exclude all 0s ahead
        int i = process.length - 1;
        while(i > 0 && process[i] == 0) i--;  // > 0 keep one 0 if there is one
         StringBuilder result = new StringBuilder();
         while(i >= 0){
             result.append((char) (process[i] + '0'));
             i--;
         }
        return result.toString();
       
    }
}

没有评论: