43. Multiply Strings (Medium)
https://leetcode.com/problems/multiply-strings/
Given two non-negative integers num1
and num2
represented as strings, return the product of num1
and num2
, also represented as a string.
Example 1:
Input: num1 = "2", num2 = "3" Output: "6"
Example 2:
Input: num1 = "123", num2 = "456" Output: "56088"
Note:
- The length of both
num1
andnum2
is < 110. - Both
num1
andnum2
contain only digits0-9
. - Both
num1
andnum2
do not contain any leading zero, except the number 0 itself. - You must not use any built-in BigInteger library or convert the inputs to integer directly.
Solutions
class Solution {
public String multiply(String num1, String num2) {
if (num1 == null || num2 == null) {
return "";
}
if (num1.equals("0") || num2.equals("0")) {
return "0";
}
String sum = "0";
for (int i = 0; i < num2.length(); i++) {
// num2 multiplies num1 one by one digit.
// Do not forget to append tailing 0
String rst = singleMul(num1, num2.charAt(num2.length() - i - 1)) + appendix0(i);
// Then sum up the result one by one digit.
sum = add(sum, rst);
}
return sum;
}
private String appendix0(int x) {
String ans = "";
for (int i = 0; i < x; i++) {
ans += "0";
}
return ans;
}
private String singleMul(String x1, char x2) {
if (x2 == '0') {
return "0";
}
if (x2 == '1') {
return x1;
}
String tmp = "";
int carry = 0;
for (int i = 0; i < x1.length(); i++) {
int a = x1.charAt(x1.length() - i - 1) - '0';
int v = a * (x2 - '0') + carry;
tmp += v % 10;
carry = v / 10;
}
if (carry != 0) {
tmp += carry;
}
return reverseString(tmp);
}
private String add(String x1, String x2) {
int len1 = x1.length();
int len2 = x2.length();
int len = Math.max(len1, len2);
String tmp = "";
int carry = 0;
for (int i = 0; i < len; i++) {
int v1 = 0;
if (i < len1) {
v1 = x1.charAt(len1 - i - 1) - '0';
}
int v2 = 0;
if (i < len2) {
v2 = x2.charAt(len2 - i - 1) - '0';
}
int v = (v1 + v2 + carry) % 10;
carry = (v1 + v2 + carry) / 10;
tmp += v;
}
if (carry != 0) {
tmp += carry;
}
return reverseString(tmp);
}
private String reverseString(String x) {
int t;
for (t = 0; t < x.length(); t++) {
if (x.charAt(x.length() - t - 1) != '0') {
break;
}
}
x = x.substring(0, x.length() - t);
String ans = "";
for (int i = 0; i < x.length(); i++) {
ans += x.charAt(x.length() - i - 1);
}
return ans;
}
}