Multiply two strings

JavaView on GFG

Time: O(n*m)

Space: O(n+m)

Problem Overview

Multiply two large numbers represented as strings.

See our study guide for structured GFG and LeetCode practice.

Intuition

Multiply two large numbers represented as strings. Grade school multiplication.

Algorithm

1Result has at most m+n digits. For each pair (i,j): result[i+j+1] += (s1[i]-48)*(s2[j]-48).
2Propagate carry right to left. Strip leading zeros.

Common Pitfalls

• Same as LC 43. Use int array of size m+n. Handle carry propagation. Check for "0" inputs.

Multiply two strings.java

Java

// Approach: Grade-school multiplication. Use an array of size m+n for partial products, then convert to string.
// Time: O(n*m) Space: O(n+m)
class Solution {
    public String multiplyStrings(String s1, String s2) {
        if (s1.equals("0") || s2.equals("0"))
            return "0";

        boolean negative = false;

        if (s1.charAt(0) == '-') {
            negative = !negative;
            s1 = s1.substring(1);
        }
        if (s2.charAt(0) == '-') {
            negative = !negative;
            s2 = s2.substring(1);
        }

        int n = s1.length();
        int m = s2.length();
        int[] result = new int[n + m];

        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                int mul = (s1.charAt(i) - '0') * (s2.charAt(j) - '0');
                int sum = mul + result[i + j + 1];

                result[i + j + 1] = sum % 10;
                result[i + j] += sum / 10;
            }
        }

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

        if (sb.length() == 0)
            return "0";

        return negative ? "-" + sb.toString() : sb.toString();
    }
}

Was this solution helpful?