Leetcode # 43. Multiply Strings

https://leetcode.com/problems/multiply-strings

First Solution

M := len(num1)
N := len(num2)

Time Complexity: O(M * N + N * (M + N)) = O(M * N + N ** 2)
Space Complexity: O(N * (M + N))
(若在長乘法乘算途中即做加法，便無須保留已計算完畢的數字)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def multiply(self, num1: str, num2: str) -> str:
    multiplication_results = []
    if num1 == "0" or num2 == "0":
      return "0"
    for i, c2 in enumerate(num2[::-1]):
      if c2 == "0":
        continue
      multiplication_results.append("")
      carry = 0
      for c1 in num1[::-1]:
        d2 = ord(c2) - 48
        d1 = ord(c1) - 48
        d2_multiply_d1 = d2 * d1 + carry
        multiplication_results[-1] = chr(d2_multiply_d1 % 10 + 48) \
                                      + multiplication_results[-1]
        carry = d2_multiply_d1 // 10
      if carry > 0:
        multiplication_results[-1] = chr(carry + 48) \
                                      + multiplication_results[-1]
      multiplication_results[-1] += "0" * i
    
    result = ""
    carry = 0
    for i in range(len(multiplication_results[-1])):
      digit_sum = carry
      carry = 0
      for k in range(len(multiplication_results)):
        rk = multiplication_results[k]
        if i >= len(rk) or rk[len(rk) - i - 1] == "0":
          continue
        digit_sum += ord(rk[len(rk) - i - 1]) - 48
      result = chr(digit_sum % 10 + 48) + result
      carry = digit_sum // 10
    
    if carry > 0:
      result = chr(carry + 48) + result
    return result

Last Updated on 2023/08/16 by A1go