Practice/Meta/Leetcode 415. Add Strings

Leetcode 415. Add Strings

CodingMust

Problem

You are given two non-negative integers represented as strings. Your task is to return the product of these two numbers, also as a string. You must implement the multiplication algorithm manually without using built-in big integer libraries or converting the entire strings to integers.

This problem simulates how multiplication would work on paper: you multiply each digit of one number by each digit of the other, keeping track of positions and carries, then sum up all the partial results.

Requirements

1. Return the product as a string representation
2. Do not use built-in multiplication on the full numbers (e.g., no int(num1) * int(num2))
3. Handle arbitrary-length input strings efficiently
4. The result should not have leading zeros (except when the result is "0")

Constraints

• 1 ≤ num1.length, num2.length ≤ 200
• num1 and num2 consist of digits only
• Both num1 and num2 do not contain leading zeros, except for the number 0 itself
• Expected time complexity: O(m × n) where m and n are the lengths of the input strings
• Expected space complexity: O(m + n) for the result array

Examples

Example 1:

Input: num1 = "2", num2 = "3" Output: "6" Explanation: Simple single-digit multiplication

Example 2:

` Input: num1 = "123", num2 = "456" Output: "56088" Explanation: 123 × 456

738 (123 × 6) 6150 (123 × 50) 49200 (123 × 400)

56088 `

Example 3:

Input: num1 = "0", num2 = "52" Output: "0" Explanation: Any number multiplied by zero is zero