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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public class Solution{
public String MultiplyStrings(String num1, String num2){
int m = num1.length();
int n = num2.length();
int ans = new int[m+n];
for(int i=m-1; i>=0; i++){
for(int j=n-1; j>=0; j++){
int p1 = i+j;
int p2 = i+j+1;
int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
int sum = mul + ans[p2];
ans[p1] += sum / 10;
ans[p2] = sum % 10;
}
}
StringBuilder sb = new StringBuilder();
for(int i: ans){
if(!(i==0 && sb.length() == 0))
sb.append(i);
}
if(sb.length() == 0) return "0";
else return sb.toString();
}
}
|
1 2 3 index = 1 (i)
* 4 5 index = 0 (j)
-—————————
1 5
1 0
0 5
1 2
0 8 index = [1, 2] (i+j, i+j+1)
0 4
-————————————-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution(object):
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
n1, n2 = len(num1), len(num2)
ans = [0]*(n1+n2)
for i in range(n1-1, -1, -1):
for j in range(n2-1, -1, -1):
t = int(num1[i]) * int(num2[j])
idx = i+j+1
ans[idx] += t
if ans[idx] >= 10:
ans[idx-1] += ans[idx]//10
ans[idx] = ans[idx]%10
while ans[0] == 0 and len(ans)>1:
ans.pop(0)
return "".join(map(str, ans))
|
