# LeetCode 43: Multiply Strings

## Problem Restatement

We are given two non-negative integers `num1` and `num2`, but they are stored as strings.

We need to return their product, also as a string.

We cannot use a built-in big integer library, and we cannot directly convert the whole input strings into integers. The official problem states this string multiplication requirement and restriction directly.

Example:

```python
num1 = "2"
num2 = "3"
```

The product is:

```python
"6"
```

Another example:

```python
num1 = "123"
num2 = "456"
```

The product is:

```python
"56088"
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two strings `num1` and `num2` |
| Output | The product as a string |
| Constraint | Do not convert the full strings directly to integers |
| Constraint | Do not use a built-in big integer library |
| Digits | Both strings contain digits only |

Function shape:

```python
def multiply(num1: str, num2: str) -> str:
    ...
```

## First Thought: Repeated Addition

A simple idea is to add `num1` to itself `num2` times.

For example:

```python
"12" * "3" = "12" + "12" + "12" = "36"
```

But this is not practical.

If `num2` is very large, repeated addition would take too long. Also, `num2` is a string, so we would still need to implement large-number addition manually.

We need a direct multiplication method.

## Key Insight

Use the same multiplication method we use by hand.

When multiplying two digits:

```python
num1[i] * num2[j]
```

their result contributes to a position determined by `i` and `j`.

If `num1` has length `m` and `num2` has length `n`, the product has at most `m + n` digits. This is the standard reason solutions allocate an array of length `m + n`.

So we create:

```python
result = [0] * (m + n)
```

Each digit multiplication contributes to two nearby positions:

```python
p1 = i + j
p2 = i + j + 1
```

The ones digit goes into `p2`.

The carry goes into `p1`.

## Algorithm

Let:

```python
m = len(num1)
n = len(num2)
```

Create a result array of size `m + n`.

Then scan both strings from right to left.

For every pair of digits:

1. Convert the characters to digits.
2. Multiply them.
3. Add the product to the current value at `result[i + j + 1]`.
4. Put the ones digit at `result[i + j + 1]`.
5. Add the carry to `result[i + j]`.

After all multiplications, remove leading zeros.

If the result is empty after removing zeros, return `"0"`.

## Walkthrough

Use:

```python
num1 = "123"
num2 = "456"
```

The result array has length:

```python
3 + 3 = 6
```

Start with:

```python
[0, 0, 0, 0, 0, 0]
```

Consider the last digits:

```python
3 * 6 = 18
```

Here:

```python
i = 2
j = 2
p1 = 4
p2 = 5
```

Place `8` at index `5` and carry `1` to index `4`:

```python
[0, 0, 0, 0, 1, 8]
```

Next:

```python
3 * 5 = 15
```

This affects positions `3` and `4`.

But index `4` already has `1`, so we add into it:

```python
15 + 1 = 16
```

Put `6` at index `4` and carry `1` to index `3`:

```python
[0, 0, 0, 1, 6, 8]
```

Continuing this process for all digit pairs gives:

```python
[0, 5, 6, 0, 8, 8]
```

After removing the leading zero, we get:

```python
"56088"
```

## Correctness

Each digit in `num1` is multiplied by each digit in `num2`.

For digits at positions `i` and `j`, their place value in the final product is determined by how far they are from the right end of their strings.

Using indices `i + j` and `i + j + 1` places each partial product into the same decimal position that grade-school multiplication would use.

The algorithm adds each partial product into the result array instead of creating separate rows. Carry is handled immediately by splitting the sum into:

```python
sum // 10
sum % 10
```

The carry moves left, and the ones digit stays in the current position.

Since every digit pair contributes exactly once, and every contribution is placed into the correct decimal position, the final array represents the true product.

Removing leading zeros does not change the numeric value. If all digits are zero, the product is `"0"`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(m * n)` | Every digit of `num1` is multiplied by every digit of `num2` |
| Space | `O(m + n)` | The result array stores at most `m + n` digits |

Here, `m = len(num1)` and `n = len(num2)`.

## Implementation

```python
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"

        m = len(num1)
        n = len(num2)
        result = [0] * (m + n)

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                digit1 = ord(num1[i]) - ord("0")
                digit2 = ord(num2[j]) - ord("0")

                product = digit1 * digit2

                p1 = i + j
                p2 = i + j + 1

                total = product + result[p2]

                result[p2] = total % 10
                result[p1] += total // 10

        return "".join(str(digit) for digit in result).lstrip("0")
```

## Code Explanation

We first handle zero:

```python
if num1 == "0" or num2 == "0":
    return "0"
```

This avoids returning an empty string after stripping leading zeros.

Then we allocate enough space for the answer:

```python
result = [0] * (m + n)
```

The nested loops visit digit pairs from right to left:

```python
for i in range(m - 1, -1, -1):
    for j in range(n - 1, -1, -1):
```

Each character is converted into an integer digit:

```python
digit1 = ord(num1[i]) - ord("0")
digit2 = ord(num2[j]) - ord("0")
```

Then we multiply:

```python
product = digit1 * digit2
```

The product contributes to these two result positions:

```python
p1 = i + j
p2 = i + j + 1
```

We add the current product to whatever is already stored at `p2`:

```python
total = product + result[p2]
```

Then we store the ones digit and carry:

```python
result[p2] = total % 10
result[p1] += total // 10
```

Finally, convert the digit array into a string and remove leading zeros:

```python
return "".join(str(digit) for digit in result).lstrip("0")
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.multiply("2", "3") == "6"
    assert s.multiply("123", "456") == "56088"
    assert s.multiply("0", "999") == "0"
    assert s.multiply("999", "999") == "998001"
    assert s.multiply("1", "12345") == "12345"
    assert s.multiply("100", "100") == "10000"
    assert s.multiply("9133", "0") == "0"

    print("all tests passed")

run_tests()
```

| Test | Expected | Reason |
|---|---:|---|
| `"2"`, `"3"` | `"6"` | Single-digit multiplication |
| `"123"`, `"456"` | `"56088"` | Standard multi-digit example |
| `"0"`, `"999"` | `"0"` | Zero product |
| `"999"`, `"999"` | `"998001"` | Large carries |
| `"1"`, `"12345"` | `"12345"` | Multiplication by one |
| `"100"`, `"100"` | `"10000"` | Zeros inside the product |