Question

43. Multiply Strings

中文文档

Description

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

 

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

 

Constraints:

• 1 <= num1.length, num2.length <= 200
• num1 and num2 consist of digits only.
• Both num1 and num2 do not contain any leading zero, except the number 0 itself.

Solutions

Solution 1: Simulating Mathematical Multiplication

Assume the lengths of $num1$ and $num2$ are $m$ and $n$ respectively, then the length of their product can be at most $m + n$.

The proof is as follows:

• If $num1$ and $num2$ both take the minimum value, then their product is ${10}^{m - 1} \times {10}^{n - 1} = {10}^{m + n - 2}$, with a length of $m + n - 1$.
• If $num1$ and $num2$ both take the maximum value, then their product is $({10}^m - 1) \times ({10}^n - 1) = {10}^{m + n} - {10}^m - {10}^n + 1$, with a length of $m + n$.

Therefore, we can apply for an array of length $m + n$ to store each digit of the product.

From the least significant digit to the most significant digit, we calculate each digit of the product in turn, and finally convert the array into a string.

Note to check whether the most significant digit is $0$, if it is, remove it.

The time complexity is $O(m \times n)$, and the space complexity is $O(m + n)$. Here, $m$ and $n$ are the lengths of $num1$ and $num2$ respectively.

class Solution:
  def multiply(self, num1: str, num2: str) -> str:
    if num1 == "0" or num2 == "0":
      return "0"
    m, n = len(num1), len(num2)
    arr = [0] * (m + n)
    for i in range(m - 1, -1, -1):
      a = int(num1[i])
      for j in range(n - 1, -1, -1):
        b = int(num2[j])
        arr[i + j + 1] += a * b
    for i in range(m + n - 1, 0, -1):
      arr[i - 1] += arr[i] // 10
      arr[i] %= 10
    i = 0 if arr[0] else 1
    return "".join(str(x) for x in arr[i:])

class Solution {
  public String multiply(String num1, String num2) {
    if ("0".equals(num1) || "0".equals(num2)) {
      return "0";
    }
    int m = num1.length(), n = num2.length();
    int[] arr = new int[m + n];
    for (int i = m - 1; i >= 0; --i) {
      int a = num1.charAt(i) - '0';
      for (int j = n - 1; j >= 0; --j) {
        int b = num2.charAt(j) - '0';
        arr[i + j + 1] += a * b;
      }
    }
    for (int i = arr.length - 1; i > 0; --i) {
      arr[i - 1] += arr[i] / 10;
      arr[i] %= 10;
    }
    int i = arr[0] == 0 ? 1 : 0;
    StringBuilder ans = new StringBuilder();
    for (; i < arr.length; ++i) {
      ans.append(arr[i]);
    }
    return ans.toString();
  }
}

class Solution {
public:
  string multiply(string num1, string num2) {
    if (num1 == "0" || num2 == "0") {
      return "0";
    }
    int m = num1.size(), n = num2.size();
    vector<int> arr(m + n);
    for (int i = m - 1; i >= 0; --i) {
      int a = num1[i] - '0';
      for (int j = n - 1; j >= 0; --j) {
        int b = num2[j] - '0';
        arr[i + j + 1] += a * b;
      }
    }
    for (int i = arr.size() - 1; i; --i) {
      arr[i - 1] += arr[i] / 10;
      arr[i] %= 10;
    }
    int i = arr[0] ? 0 : 1;
    string ans;
    for (; i < arr.size(); ++i) {
      ans += '0' + arr[i];
    }
    return ans;
  }
};

func multiply(num1 string, num2 string) string {
  if num1 == "0" || num2 == "0" {
    return "0"
  }
  m, n := len(num1), len(num2)
  arr := make([]int, m+n)
  for i := m - 1; i >= 0; i-- {
    a := int(num1[i] - '0')
    for j := n - 1; j >= 0; j-- {
      b := int(num2[j] - '0')
      arr[i+j+1] += a * b
    }
  }
  for i := len(arr) - 1; i > 0; i-- {
    arr[i-1] += arr[i] / 10
    arr[i] %= 10
  }
  i := 0
  if arr[0] == 0 {
    i = 1
  }
  ans := []byte{}
  for ; i < len(arr); i++ {
    ans = append(ans, byte('0'+arr[i]))
  }
  return string(ans)
}

function multiply(num1: string, num2: string): string {
  if (num1 === '0' || num2 === '0') {
    return '0';
  }
  const m: number = num1.length;
  const n: number = num2.length;
  const arr: number[] = Array(m + n).fill(0);
  for (let i: number = m - 1; i >= 0; i--) {
    const a: number = +num1[i];
    for (let j: number = n - 1; j >= 0; j--) {
      const b: number = +num2[j];
      arr[i + j + 1] += a * b;
    }
  }
  for (let i: number = arr.length - 1; i > 0; i--) {
    arr[i - 1] += Math.floor(arr[i] / 10);
    arr[i] %= 10;
  }
  let i: number = 0;
  while (i < arr.length && arr[i] === 0) {
    i++;
  }
  return arr.slice(i).join('');
}

impl Solution {
  pub fn multiply(num1: String, num2: String) -> String {
    if num1 == "0" || num2 == "0" {
      return String::from("0");
    }
    let (num1, num2) = (num1.as_bytes(), num2.as_bytes());
    let (n, m) = (num1.len(), num2.len());
    let mut res = vec![];
    for i in 0..n {
      let a = num1[n - i - 1] - b'0';
      let mut sum = 0;
      let mut j = 0;
      while j < m || sum != 0 {
        if i + j == res.len() {
          res.push(0);
        }
        let b = num2.get(m - j - 1).unwrap_or(&b'0') - b'0';
        sum += a * b + res[i + j];
        res[i + j] = sum % 10;
        sum /= 10;
        j += 1;
      }
    }
    res.into_iter()
      .rev()
      .map(|v| char::from(v + b'0'))
      .collect()
  }
}

public class Solution {
  public string Multiply(string num1, string num2) {
    if (num1 == "0" || num2 == "0") {
      return "0";
    }

    int m = num1.Length;
    int n = num2.Length;
    int[] arr = new int[m + n];

    for (int i = m - 1; i >= 0; i--) {
      int a = num1[i] - '0';
      for (int j = n - 1; j >= 0; j--) {
        int b = num2[j] - '0';
        arr[i + j + 1] += a * b;
      }
    }

    for (int i = arr.Length - 1; i > 0; i--) {
      arr[i - 1] += arr[i] / 10;
      arr[i] %= 10;
    }

    int index = 0;
    while (index < arr.Length && arr[index] == 0) {
      index++;
    }

    StringBuilder ans = new StringBuilder();
    for (; index < arr.Length; index++) {
      ans.Append(arr[index]);
    }

    return ans.ToString();
  }
}