Multiply Strings @LeetCode

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.

	package leetcode;
	import java.math.BigInteger;
	/**
	* Solution: understand multiply deeply, multiply digit by digit, take care of carry and trim 0;
	*
	* 385 * 97 ones 5*7 tens 8*7+5*9 hundreds 3*7+8*9
	* ==> d[i+j] = Character.getNumeric(length - 1 - i) * Character.getNumeric(length - 1 -j)
	* new result length = num1.length()+num2.length()
	*
	* 每一位digit的计算都是两边的结果，比如 i=1, j=2, i=2, j=1. 所以累计结果的时候product 需要加上 digit[i+j+1].跟求sum不同，求积别忘了.
	* 每次乘完一轮记得把carry 复制 digit[i+j+1]. 此时因为j--了，已经顶上高位了. 这是最高位进位，跟求sum最后判断 carry道理一样.
	* 新的一轮carry 要去清零
	*
	* Reference: http://leetcodenotes.wordpress.com/2013/10/20/leetcode-multiply-strings
	* -%E5%A4%A7%E6%95%B4%E6%95%B0%E7%9A%84%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B9%98%E6%B3%95/comment-page-1/#comment-122
	* @author jeffwan
	* @date Apr 4, 2014
	*/
	public class MultiplyStrings {
	public String multiply(String num1, String num2) {
	if (num1 == null || num2 == null) {
	return null;
	}
	int length = num1.length() + num2.length();
	int[] digits = new int[length];
	int carry, product;
	int i, j;
	for (i = num1.length() - 1; i >= 0; i--) {
	carry = 0;
	for (j = num2.length() - 1; j >= 0; j--){
	product = carry + digits[i + j + 1]
	+ Character.getNumericValue(num1.charAt(i)) * Character.getNumericValue(num2.charAt(j));
	carry = product / 10;
	digits[i + j + 1] = product % 10;
	}
	digits[i + j + 1] = carry; // The last carry should assign the first digit.
	}
	StringBuilder sb = new StringBuilder();
	i = 0;
	// 11 * 10 = 110. digits[4]. So we must trim first 0, i < length - 1. leave last 0 for result!.
	while (i < length - 1 && digits[i] == 0) {
	i++;
	}
	while (i < length) {
	sb.append(digits[i++]);
	}
	return sb.toString();
	}
	// LeetCode can't find class BigInteger
	public String multiply2(String num1, String num2) {
	BigInteger m = new BigInteger(num1);
	BigInteger n = new BigInteger(num2);
	BigInteger result = m.multiply(n);
	return result.toString();
	}
	}

view raw MultiplyStrings.java hosted with ❤ by GitHub