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.
• Converting the input string to integer is NOT allowed.
• You should NOT use internal library such as BigInteger.

``````/**
* Created by gzdaijie on 16/5/21
* 翻转数字, 观察可知 result[i + j] = nums[i] * num[j] % 10
* 注意处理进位即可
*/
public class Solution {
public String multiply(String num1, String num2) {
char[] str1 = num1.toCharArray();
char[] str2 = num2.toCharArray();
char[] result = new char[str1.length + str2.length];

for (int i = 0; i < result.length; i++) result[i] = '0';

reverse(str1);
reverse(str2);

int tmp = 0;
for (int i = 0; i < str1.length; i++) {
for (int j = 0; j < str2.length; j++) {
tmp = (str1[i] - '0') * (str2[j] - '0') + (result[i + j] - '0');
result[i + j] =  (char)(tmp % 10 + '0');
// 将进位预存储在前一位中
result[i + j + 1] += tmp / 10;
}
}

reverse(result);

// 去除字符串前所有的 '0'
int count = 0;
for (int i = 0; i < result.length && result[i] == '0'; i++, count++); /* empty */

if (count == result.length) return "0";
return new String(result, count, result.length - count);
}

private void reverse(char[] chars) {
int len = chars.length;
char ch;
for (int i = 0; i < len/2; i++) {
ch = chars[i];
chars[i] = chars[len - i - 1];
chars[len - i - 1] = ch;
}
}
}
``````
updated 2016-05-21 23:33:00