Multiply-Strings.md

##Multiply Strings

Total Accepted: 59422 Total Submissions: 254425 Difficulty: Medium
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.
Converting the input string to integer is NOT allowed.
You should NOT use internal library such as BigInteger.

####思路

• 参考1
• 参考2
• 把乘法过程画出来
• 就会发现第k位结果是第i位乘以第k位的和(i + j == k)

public class Solution {

	public 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();
	}

}