【LeetCode】43. Multiply Strings

问题描述

https://leetcode.com/problems/multiply-strings/#/description

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

• The length of both num1 and num2 is < 110.
• Both num1 and num2 contains only digits 0-9.
• Both num1 and num2 does not contain any leading zero.
• You must not use any built-in BigInteger library or convert the inputs to integer directly.

问题分析

看下面这个竖式计算过程

     1 5           ->a
   1 1 9           ->b
________
   1 3 5           ->c
   1 5             ->d
 1 5               ->e
________
 1 7 8 5           ->f

先是数b的每一位数分别与数a的每位数相乘，得到c，d，e三个数，然后是c，d，e三数相加。

因为是大数加法，我们必需使用数组表示，结果f就是一个数组，每一位都是一轮轮的计算结果累加以及上一位的进位得来的。根据这个思想，就可以解决问题了(参考自solutions)。

代码

public String multiply(String num1, String num2) {
	    	int[] product = new int[num1.length() + num2.length()];
	    	for(int i=num1.length() - 1; i>=0;i--) {
	    		int a = num1.charAt(i) - '0';
	    		for(int j = num2.length() - 1; j >=0; j--) {
	    			int b = num2.charAt(j) - '0';
	    			int cur = product.length - 2 - i - j;
	    			product[cur] += a * b;
	    			product[cur+1] += product[cur] / 10;
	    			product[cur] %= 10;
	    		}
	    	}
	    	StringBuffer sb = new StringBuffer();
	    	for(int i = product.length - 1; i > 0; i--) {
	    		if(sb.length() == 0 && product[i] == 0) {
	    			continue;
	    		}
	    		sb.append(product[i]);
	    	}
	    	sb.append(product[0]);
	    	return sb.toString();
	    }