---
title: Multiply Strings
difficulty: Medium
category: String
leetcode_id: 43
revision_count: 1
last_revision: 2026-09-12
---

# Multiply Strings

> **LeetCode:** [#43](https://leetcode.com/problems/multiply-strings/)
> **Сложность:** Medium
> **Категория:** String

## Условие

Даны два неотрицательных целых числа в виде строк `num1` и `num2`. Вернуть их произведение в виде строки. Нельзя преобразовывать строки в Integer напрямую (могут быть длиной до 200 символов). Умножение столбиком: перемножаем каждую цифру `num1` с каждой цифрой `num2`, накапливаем сумму в массиве, в конце собираем результат.

```
Input:  num1 = "2", num2 = "3"      →  Output: "6"
Input:  num1 = "123", num2 = "456"  →  Output: "56088"
Input:  num1 = "0", num2 = "0"      →  Output: "0"
```

## Ключевая идея

Моделируем умножение столбиком: для позиций `i` (в `num1`) и `j` (в `num2`) произведение цифр попадает в позиции `i+j` (перенос) и `i+j+1` (единицы) результирующего массива. Двигаемся справа налево по обоим числам, затем собираем строку, пропуская ведущие нули.

## Оценка сложности

- **Время:** O(n * m), где n, m — длины строк (каждую цифру num1 перемножаем с каждой цифрой num2)
- **Память:** O(n + m) — массив результата

## Решение (Ruby)

```ruby
# @param {String} num1
# @param {String} num2
# @return {String}
def multiply(num1, num2)
  return "0" if num1 == "0" || num2 == "0"

  n, m = num1.size, num2.size
  result = Array.new(n + m, 0)

  (n - 1).downto(0) do |i|
    (m - 1).downto(0) do |j|
      mul = num1[i].to_i * num2[j].to_i
      p1, p2 = i + j, i + j + 1
      sum = mul + result[p2]
      result[p2] = sum % 10
      result[p1] += sum / 10
    end
  end

  result.drop_while { |d| d == 0 }.join
end
```

## Разбор на примере

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

i=2 (num1[2]='3'), j=2 (num2[2]='6'):
  mul = 3*6 = 18, p1=4, p2=5
  result[5] = 18%10 = 8, result[4] += 1 → [0,0,0,0,1,8]

i=2, j=1 (num2[1]='5'):
  mul = 3*5 = 15, p1=3, p2=4
  result[4] = 15+1=16%10 = 6, result[3] += 1 → [0,0,0,1,6,8]

i=2, j=0 (num2[0]='4'):
  mul = 3*4 = 12, p1=2, p2=3
  result[3] = 12+1=13%10 = 3, result[2] += 1 → [0,0,1,3,6,8]

i=1 (num1[1]='2'), j=2:
  mul = 2*6 = 12, p1=3, p2=4
  result[4] = 12+6=18%10 = 8, result[3] += 1 → [0,0,1,4,8,8]

i=1, j=1:
  mul = 2*5 = 10, p1=2, p2=3
  result[3] = 10+4=14%10 = 4, result[2] += 1 → [0,0,2,4,8,8]

i=1, j=0:
  mul = 2*4 = 8, p1=1, p2=2
  result[2] = 8+2=10%10 = 0, result[1] += 1 → [0,1,0,4,8,8]

i=0 (num1[0]='1'), j=2:
  mul = 1*6 = 6, p1=2, p2=3
  sum = 6 + result[3]=4 = 10 → result[3]=0, result[2] += 1 → [0,1,1,0,8,8]

i=0, j=1:
  mul = 1*5 = 5, p1=1, p2=2
  sum = 5 + result[2]=1 = 6 → result[2]=6 → [0,1,6,0,8,8]

i=0, j=0:
  mul = 1*4 = 4, p1=0, p2=1
  sum = 4 + result[1]=1 = 5 → result[1]=5 → [0,5,6,0,8,8]

Result: drop_while(&:zero?) → "56088"
```

## Edge Cases

- **Один из множителей — ноль**: `"0" * "123" = "0"` — проверка в начале, возвращаем `"0"` сразу.
- **Ведущие нули в результате**: массив может начинаться с нулей, убираем `drop_while`.
- **Разная длина чисел**: всегда работаем как `n * m`, порядок не важен.
- **Максимальная длина**: до 200 цифр каждая → результат до 400 цифр. Прямое преобразование в Integer запрещено условием (в языках с фиксированной длиной — переполнение, в Ruby — просто не тот путь и нарушение условия).
- **Однозначные числа**: `"2" * "3" = "6"` — корректно попадает в `result[0]`.

## Типичные ошибки

1. ❌ **Забыть `return "0"` для нулевого множителя** — алгоритм даст `"000...0"` вместо `"0"`.
2. ❌ **Перепутать p1 и p2**: `p1 = i + j` (перенос), `p2 = i + j + 1` (единицы). Легко запомнить: младшая позиция — больше индекс.
3. ❌ **Неверный порядок обхода**: идём справа налево (`downto`), чтобы перенос шёл влево (меньший индекс).
4. ❌ **Собирать результат без `drop_while`**: массив хранит позиционные разряды и почти всегда начинается с ведущих нулей, без их удаления получим `"056088"` вместо `"56088"`. Случай `"0" * "0"` уже перехвачен ранним return.
5. ❌ **Использовать `to_i` для всего числа**, например `(num1.to_i * num2.to_i).to_s` — запрещено условием задачи (числа до 200 цифр), хоть для коротких чисел и работает.

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Через Integer: `(num1.to_i * num2.to_i).to_s` | O(n+m) | O(1) | работает только для коротких чисел |
| **Умножение столбиком с массивом** | **O(n*m)** | **O(n+m)** | **финальное решение, стандарт для интервью** |
| Karatsuba (разделяй и властвуй) | O(n^1.585) | O(n) | быстрее, но сложнее; не требуется на интервью |
| FFT (быстрое преобразование Фурье) | O(n log n) | O(n) | оверкилл для 200 цифр |

### Ruby built-in (не для интервью)

```ruby
(num1.to_i * num2.to_i).to_s
```

> **Важно:** на интервью пишут руками. `to_i` годен только как быстрая проверка результата.

## Заметки после повторения

_Что забыл? Что пошло не так? На чём застрял? Заполни после каждой тренировки._