https://leetcode.com/problems/multiply-strings/
Multiply Strings
Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.
It is not a very funny problem that can test you in the interview.
Refer Idea here:
https://leetcode.com/discuss/33951/ac-solution-in-java-with-explanation
Refer Python Code here:
https://leetcode.com/discuss/50707/simple-python-solution-18-lines
Updated 2016-10-31:
Actually this problem can be solved elegantly.
Code
class Solution(object):
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
m, n = len(num1), len(num2)
pos = [0] * (m+n)
for i in xrange(m-1, -1, -1):
for j in xrange(n-1, -1, -1):
d1, d2 = int(num1[i]), int(num2[j])
sum = d1 * d2 + pos[i+j+1]
pos[i+j] += sum/10
pos[i+j+1] = sum % 10
res = ''
for p in pos:
if not (not res and not p):
res += str(p)
return res if res else '0'
Idea
Don’t worry about pos[i+j] += sum/10 (line 15) will become greater than 10. It will ultimately be taken mod when smaller i or j is traversed.
Reference: https://discuss.leetcode.com/topic/30508/easiest-java-solution-with-graph-explanation/2