Core Insight Name the mathematical relationship first, then apply it consistently to every position or digit.
Common Pitfall Write down index and boundary conditions before mutating an in-place structure.
Description
Multiply two non-negative integers represented as strings.
Constraints
- Time Complexity:
O(m·n) - Space Complexity:
O(m+n)
Tags
mathstringsimulation
Implementation Plan Translate the invariant into these small, testable moves.
- Identify the formula or transformation.
- Set boundary conditions.
- Process each required position.
- Return the transformed result.
def multiply(num1, num2):
if "0" in [num1, num2]:
return "0"
res = [0] * (len(num1) + len(num2))
num1, num2 = num1[::-1], num2[::-1]
for i1 in range(len(num1)):
for i2 in range(len(num2)):
digit = int(num1[i1]) * int(num2[i2])
res[i1 + i2] += digit
res[i1 + i2 + 1] += (res[i1 + i2] // 10)
res[i1 + i2] = res[i1 + i2] % 10
res, beg = res[::-1], 0
while beg < len(res) and res[beg] == 0:
beg += 1
res = map(str, res[beg:])
return "".join(res)