Multiply Strings
Problem
Given two non-negative integers num1
and num2
represented as strings, return the product of num1
and num2
.
Note:
- The length of both num1 and num2 is < 110.
- Both num1 and num2 contains only digits 0-9.
- Both num1 and num2 does not contain any leading zero.
- You must not use any built-in BigInteger library or convert the inputs to integer directly.
Solution
public class Solution {
public String multiply(String num1, String num2) {
int m = num1.length(), n = num2.length();
int[] nums = new int[m+n];
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
int start = i + j, end = i + j + 1;
int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
int sum = mul + nums[end];
nums[end] = sum % 10;
nums[start] += sum / 10;
}
}
StringBuilder sb = new StringBuilder();
for (int num : nums) if (!(sb.length() == 0 && num == 0)) sb.append(num);
return sb.length() == 0 ? "0" : sb.toString(); //Need to check "0" + "0" case
}
}
Analysis
We cannot use the exact same idea of "Adding Strings" because multiplication is different from addiction
Therefore, we completely manipulate the procedure of multiplication of two numbers
You can understand this solution better if you multiply two numbers on a paper with your pen
At the end, we just need to check corner case in order to return the correct result