43. Multiply Strings

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.

Solution:

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")){
            return "0";
        }
        // 123 
        // 456

        int m = num1.length(); // 3
        int n = num2.length(); //3

        int[] ans = new int[m + n];
        //  0  1  2  3  4  5
        // [0, 0, 0, 12, 15, 18 ]   3 + 3 
        for (int i = m - 1; i >= 0; i--){// i = 3 -1 =2 ; 
            int digit = num1.charAt(i) - '0';
            // 3 - '0' = 3
            for (int j = n - 1; j >= 0; j--){ // 3-1 = 2 , 1
                int digit2 = num2.charAt(j) - '0';
                ans[i + j + 1] = ans[i + j + 1] + digit * digit2;
                // ans[2 + 2+ 1] = ans[2+ 2+ 1] + 3 * 6 = 
                // ans [5] = ans[5] + 18 = 18
                // ans[2+1 +1 ] = ans[2+1+1] + 3 * 5
                // ans[4] = ans[5] + 15 = 15
                // ans[3] = ans[3] + 3 * 4 = 0 + 12 = 12
            }
        }
        /*
        // like we do the multiple
        //  4    5   6 
        //x 1    2   3 
        // ----------------
        //           18
        //      15
        // 12
        //      12
        // 10
        8
            6
        5
    4
        ------------------------
    4  13  28   27   18 
        */




        int carry = 0;
        for (int i = ans.length - 1; i >= 0; i--){
            ans[i] = ans[i] + carry;
            carry = ans[i] / 10;
            ans[i] = ans[i] % 10;
        }
        //        4  13  28   27   18  
        //        5    6  0    8    8 
        // 
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < ans.length; i++){
            if (i == 0 && ans[i] == 0){
                continue;
            }
            sb.append(ans[i]);
        }

        return sb.toString();
    }
}

// TC: O(n^2)
// SC: O(n)