Skip to content

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:]))