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.
Solution
Just like what we do when multiplying integers.
Complexity
时间复杂度 O(n2 ),空间复杂度 O(n)
Code
public class Solution {
public String multiply(String num1, String num2) {
int l1 = num1.length(), l2 = num2.length();
if (l1 == 0 || l2 == 0) return new String("");
if (num1.charAt(0) == '0' || num2.charAt(0) == '0') return new String("0");
StringBuffer sb = new StringBuffer();
int[] res = new int[l1+l2];
for (int i = 0; i < l1; ++i) {
for (int j = 0; j < l2; ++j) {
res[i+j+1] += (num1.charAt(i)-'0') *(num2.charAt(j)-'0');
}
}
int c = 0;
for (int i = res.length - 1; i>=1; --i) {
res[i] += c;
c = res[i] / 10;
res[i] = res[i] % 10;
sb.insert(0,res[i]);
}
if (c !=0 || res[0] != 0) {
sb.insert(0,c+res[0]);
}
return sb.toString();
}
}