algoadvance

Leetcode 43. Multiply Strings

Problem Statement

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

Note:

  1. The numbers represented by num1 and num2 are non-negative.
  2. You must not use any built-in BigInteger library or directly convert the inputs to integers.

Clarifying Questions

  1. Input Constraints:
    • What is the maximum length of num1 and num2?
      • Assumption: The length of the strings num1 and num2 will not exceed 200.
  2. Output Specification:
    • Should the result handle leading zeroes?
      • Assumption: The result should not contain leading zeros unless the result is “0”.

Strategy

To solve this problem without converting the entire string to an integer (which might overflow), we can employ elementary school multiplication:

  1. Initialize: Create an array result of size num1.length() + num2.length() to store intermediate results.
  2. Multiply: Loop through each digit of num1 and num2, multiply the digits, and store the results in appropriate positions in the result array.
  3. Carry Handling: Handle carry-over values as you populate the result array.
  4. Construct the Result: Convert the result array to a string while skipping any leading zeros.

Code

Here is the Java implementation of the solution:

public class Solution {
    public String multiply(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        int[] result = new int[len1 + len2];

        // Reverse iterate both strings
        for (int i = len1 - 1; i >= 0; i--) {
            for (int j = len2 - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j;
                int p2 = i + j + 1;
                int sum = mul + result[p2];

                result[p1] += sum / 10;
                result[p2] = sum % 10;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int num : result) {
            if (!(sb.length() == 0 && num == 0)) { // Skip leading zeros
                sb.append(num);
            }
        }

        return sb.length() == 0 ? "0" : sb.toString();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.multiply("123", "456")); // Expected output: "56088"
        System.out.println(sol.multiply("0", "2345"));   // Expected output: "0"
        System.out.println(sol.multiply("999", "999"));  // Expected output: "998001"
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI