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. Note2: Your answer should not have leading zeroes. For example, 00 is not a valid answer.
For example, given strings "12", "10", your answer should be “120”.
Method:
Literally implement multiplication
Solution: Time: O(m * n) Space: O(m + n)
public class Solution {
// 1 3 4
// 1 2 5
// 6 7 0
// 2 6 8
// 1 3 4
public String multiply(String A, String B) {
String prod = "0";
for (int i = B.length() - 1; i >= 0; i --) { // O(n)
char b = B.charAt(i);
String temp = mul(A, b); // O(m)
StringBuilder offset = new StringBuilder();
for (int j = i; j < B.length() - 1; j ++) {
offset.append("0");
}
temp = temp + offset.toString();
prod = add(prod, temp); // O(m)
}
StringBuilder result = new StringBuilder(prod);
while (result.length() > 1 && result.charAt(0) == '0') {
result.deleteCharAt(0);
}
return result.toString();
}
private String mul(String A, char b) {
int carry = 0;
int i = A.length() - 1;
StringBuilder prod = new StringBuilder();
int bVal = b - '0';
while (i >= 0) {
char c = A.charAt(i);
int aVal = c - '0';
int num = (aVal * bVal + carry) % 10;
carry = (aVal * bVal + carry) / 10;
prod.append(String.valueOf(num));
i --;
}
if (carry > 0) {
prod.append(String.valueOf(carry));
}
return prod.reverse().toString();
}
private String add(String A, String B) {
int carry = 0;
int i = A.length() - 1;
int j = B.length() - 1;
StringBuilder sum = new StringBuilder();
while (i >= 0 && j >= 0) {
char a = A.charAt(i);
int aVal = a - '0';
char b = B.charAt(j);
int bVal = b - '0';
int num = (aVal + bVal + carry) % 10;
carry = (aVal + bVal + carry) / 10;
sum.append(String.valueOf(num));
i --;
j --;
}
while (i >= 0) {
char a = A.charAt(i);
int aVal = a - '0';
int num = (aVal + carry) % 10;
carry = (aVal + carry)/ 10;
sum.append(String.valueOf(num));
i --;
}
while (j >= 0) {
char b = B.charAt(j);
int bVal = b - '0';
int num = (bVal + carry) % 10;
carry = (bVal + carry)/ 10;
sum.append(String.valueOf(num));
j --;
}
if (carry > 0) {
sum.append(String.valueOf(carry));
}
return sum.reverse().toString();
}
}