BiruLyu
5/25/2017 - 7:07 AM

## 43. Multiply Strings.java

``````class Solution(object):
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
m = len(num1);
n = len(num2);

res = [ 0 for i in xrange(m + n)];

for i in xrange(m - 1, -1, -1):
for j in xrange(n - 1, -1, -1):
temp = int(num1[i]) * int(num2[j]) + res[i + j + 1];
res[i + j] += temp / 10;
res[i + j + 1] = temp % 10;

resString = "";
for i in res:
if len(resString) == 0 and i == 0:
continue;
resString += str(i);

return '0' if len(resString) == 0 else resString;

"""
TESTCASES:
Input:
"0"
"0"
"999"
"99"

Output:
"0"
"98901"

"""
"""
##########
#Start from right to left, perform multiplication on every pair of digits, and add them together. Let's draw the process! From the following draft, we can immediately conclude:

# `num1[i] * num2[j]` will be placed at indices `[i + j`, `i + j + 1]`
#Multiplication

1 2 3
4 5
------
1 5
1 0
0 5
1 2
0 8
0 4
--------------
0 1 2 3 4   [index]

"""
``````
``````public class Solution {
public String multiply(String num1, String num2) {
int len1 = num1.length();
int len2 = num2.length();

int[] res = new int[ len1 + len2];

for(int i = len1 - 1; i >= 0; i-- ){
for(int j = len2 - 1; j >=0; j-- ){
int temp = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + res[i + j + 1];
res[i + j] += temp / 10;
res[i + j + 1] = temp % 10;
}
}

StringBuilder resString = new StringBuilder();

for(int i = 0; i < res.length; i++){
if( resString.length() == 0 && res[i] == 0){
continue;
}
resString.append(res[i]);
}

return resString.length() == 0 ? "0" : resString.toString();
}
}

/*
"0"
"0"
"999"
"99"
"100"
"100"

1 2 3
4 5
------
1 5
1 2
1 0    //res[i + j] += temp / 10; 累加！！
0 8
0 5
0 4
--------------
0 5 5 3 5
0 1 2 3 4   [index]
*/``````