Multiply Strings 两个字符串代表数字相乘@LeetCode

这道题一开始觉得很麻烦，后来参考了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

才知道有如此优雅的写法，这样的写法一遍就可以写出bug free的代码。

思路：

1 翻转string

2 建立数组，双层循环遍历两个string，把单位的乘积累加到数组相应的位置

3 处理进位并输出

4 注意前导零的corner case

package Level4;

/**
 * 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.
 * 
 */
public class S43 {

	public static void main(String[] args) {
		String num1 = "0";
		String num2 = "0";
		System.out.println(multiply(num1, num2));
	}

	public static String multiply(String num1, String num2) {
		// 先把string翻转
		String n1 = new StringBuilder(num1).reverse().toString();
		String n2 = new StringBuilder(num2).reverse().toString();
		
		int[] d = new int[n1.length()+n2.length()];		// 构建数组存放乘积
		for(int i=0; i<n1.length(); i++){
			for(int j=0; j<n2.length(); j++){
				d[i+j] += (n1.charAt(i)-'0') * (n2.charAt(j)-'0');		// 在正确位置累加乘积
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<d.length; i++){
			int digit = d[i]%10;		// 当前位
			int carry = d[i]/10;		// 进位
			if(i+1<d.length){
				d[i+1] += carry;
			}
			sb.insert(0, digit);		// prepend
		}
		
		// 移除前导零
		while(sb.charAt(0)=='0' && sb.length()>1){
			sb.deleteCharAt(0);
		}
		return sb.toString();
	}

}