# 43. Multiply Strings¶

• Time: $O(|\texttt{num1}||\texttt{num2}|)$
• Space: $O(|\texttt{num1}| + |\texttt{num2}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public: string multiply(string num1, string num2) { string s(num1.length() + num2.length(), '0'); for (int i = num1.length() - 1; i >= 0; --i) for (int j = num2.length() - 1; j >= 0; --j) { const int mult = (num1[i] - '0') * (num2[j] - '0'); const int sum = mult + (s[i + j + 1] - '0'); s[i + j] += sum / 10; s[i + j + 1] = '0' + sum % 10; } const int i = s.find_first_not_of('0'); return i == string::npos ? "0" : s.substr(i); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public String multiply(String num1, String num2) { final int m = num1.length(); final int n = num2.length(); StringBuilder sb = new StringBuilder(); int[] pos = new int[m + n]; for (int i = m - 1; i >= 0; --i) for (int j = n - 1; j >= 0; --j) { final int multiply = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); final int sum = multiply + pos[i + j + 1]; pos[i + j] += sum / 10; pos[i + j + 1] = sum % 10; } for (final int p : pos) if (p > 0 || sb.length() > 0) sb.append(p); return sb.length() == 0 ? "0" : sb.toString(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution: def multiply(self, num1: str, num2: str) -> str: s = [0] * (len(num1) + len(num2)) for i in reversed(range(len(num1))): for j in reversed(range(len(num2))): mult = int(num1[i]) * int(num2[j]) summ = mult + s[i + j + 1] s[i + j] += summ // 10 s[i + j + 1] = summ % 10 for i, c in enumerate(s): if c != 0: break return ''.join(map(str, s[i:]))