问题描述
https://leetcode.com/problems/multiply-strings/
解决思路
每一位相乘，和做正常乘法过程类似。
代码
class Solution {
public String multiply(String num1, String num2) {
if(num1 == null || num2 == null) return "0";
//to store the result of num1 * num2
int[] digits = new int[num1.length() + num2.length()];
for(int i = num1.length() - 1; i >= 0; i--){
for(int j = num2.length() - 1; j >= 0 ; j--){
int product = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
int p1 = i + j, p2 = i + j + 1;
int sum = product + digits[p2];
digits[p1] += sum / 10;
digits[p2] = sum % 10;
}
}
StringBuilder res = new StringBuilder();
for(int digit : digits){
//digits == [0 0 0 1 0 3]
if(!(digit == 0 && res.length() == 0)){
res.append(digit);
}
}
return res.length() == 0 ? "0" : res.toString();
}
}
复杂度分析
- 时间复杂度：O(n^2)
- 空间复杂度：O(n)
