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.

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.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

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

Output: "6"

Example 2

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

Output: "56088"

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")) return "0";
        
        int num1Len = num1.length(),
            num2Len = num2.length();
        
        int[] product = new int[num1Len+num2Len];

        for(int i = num1Len-1; i >= 0; i--) {
            int val1 = num1.charAt(i)-'0';
            for(int j = num2Len-1; j >= 0; j--) {
                int val = (val1 * (num2.charAt(j)-'0'));
                
                int p1 = i+j;
                int p2 = i+j+1;
                
                val += product[p2];
                product[p1] += val/10;
                product[p2] = val%10;
            }
        }
        
        StringBuilder result = new StringBuilder();
        for(int val: product) {
            if(!(val == 0 && result.length() == 0)) {
                result.append(val);
            }
        }

        return result.toString();
    }
}

Follow up