43. Multiply Strings
We solved this problem by simulating vertical multiplication which factoring the multiplier into coefficient and exponent. For example, 123 * 456 = 123 * 4 * 10^2 + 123 * 5 * 10^1 + 123 * 6 * 10^0.
class Solution {
private String addString(String num1, String num2) {
int i = num1.length() - 1;
int j = num2.length() - 1;
StringBuilder builder = new StringBuilder();
int carry = 0;
while (i >= 0 || j >= 0) {
int iNum = (i >= 0) ? (num1.charAt(i) - '0') : 0;
int jNum = (j >= 0) ? (num2.charAt(j) - '0') : 0;
int sum = iNum + jNum + carry;
carry = sum / 10;
builder.append(sum % 10);
i--;
j--;
}
if (carry == 1) {
builder.append(1);
}
return builder.reverse().toString();
}
private String helper(String multiplicand, char multiplier, int exp) {
StringBuilder builder = new StringBuilder();
int carry = 0;
for (int i = multiplicand.length() - 1; i >= 0; i--) {
char num = multiplicand.charAt(i);
int product = (num - '0') * (multiplier - '0') + carry;
carry = product / 10;
builder.append(product % 10);
}
if (carry != 0) {
builder.append(carry);
}
builder.reverse();
for (int i = 0; i < exp; i++) {
builder.append('0');
}
return builder.toString();
}
public String multiply(String num1, String num2) {
if ("0".equals(num1) || "0".equals(num2)) {
return "0";
}
String sum = "0";
int count = 0;
for (int i = num2.length() - 1; i >= 0; i--) {
char c = num2.charAt(i);
String temp = helper(num1, c, count);
sum = addString(sum, temp);
count++;
}
return sum;
}
}