LeetCode 43: Multiply Strings Solution

Master LeetCode problem 43 (Multiply Strings), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

43. Multiply Strings

Medium

Math String Simulation

Problem Explanation

Explanation

To multiply two numbers represented as strings num1 and num2, we can simulate the multiplication process that we do manually. We iterate through each digit of num1 from right to left and multiply it with each digit of num2 from right to left. We keep track of the product at each position and then sum up all these intermediate products to get the final result.

Algorithmic Idea

Initialize a result array of size num1.length() + num2.length().
Iterate through each digit of num1 from right to left.
Iterate through each digit of num2 from right to left.
Multiply the current digits and add the product to the appropriate position in the result array.
After both loops finish, convert the result array to a string while handling any leading zeros.

Time Complexity

The time complexity of this algorithm is O(m * n), where m is the length of num1 and n is the length of num2.

Space Complexity

The space complexity of this algorithm is O(m + n) to store the result array.

Solution Code

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

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int sum = mul + result[i + j + 1];
                result[i + j] += sum / 10;
                result[i + j + 1] = sum % 10;
            }
        }

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

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 43 (Multiply Strings)?

This page provides optimized solutions for LeetCode problem 43 (Multiply Strings) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 43 (Multiply Strings)?

The time complexity for LeetCode 43 (Multiply Strings) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 43 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 43 in Java, C++, or Python.

Back to LeetCode Solutions