43. Multiply Strings.md

43. Multiply Strings

Question

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. tag:

• 模拟

Solution

从右到做扫描num1,num2， 对每一对数字执行乘法操作， 逐步累加。 处理过程如图所示，

num1[i]*num2[j] 相乘结果的下标为[i+j, i+j+1]

java

	public String multiply(String num1, String num2) {
		int len1 = num1.length(), len2 = num2.length();
		int[] res = new int[len1 + len2];
		for (int i = 0; i < len1; i++)
			for (int j = 0; j < len2; j++) {
				int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
				int sum = mul + res[i + j + 1];
				res[i + j] += sum / 10;
				res[i + j + 1] = sum % 10;
			}
		StringBuffer sb = new StringBuffer();
		for (int p : res) if (!(sb.length()==0 && p==0)) sb.append(p);
		return sb.length() == 0 ? "0" : sb.toString();
	}

go