Isomorphic Strings

Лёгкая№205два словаря

Даны две строки одной длины, s и t. Нужно понять, можно ли заменить буквы s так, чтобы получилась t: одна и та же буква всегда меняется на одну и ту же, а две разные не могут стать одной. Наш пример: «stone» и «ladle» — нет: в l пришлось бы превратить и s, и n.

205 Isomorphic StringsРазбор · 1×

Пример: s = «stone», t = «ladle». Под ними оба словаря: во что превращается каждая буква s и откуда взялась каждая буква t.

st0s1t2o3n4eladletoTs → t—toSt → s—
ещё не дошлитекущая парапровереноконфликт

toT будет говорить, во что превращается каждая буква s

01/22
сначала · назад · пуск · шаг
Скорость
1function isIsomorphic(s, t):
2 toT = empty map
3 toS = empty map
4 for i from 0 to len(s) - 1:
5 a = s[i]; b = t[i]
6 if a in toT and toT[a] != b:
7 return false
8 if b in toS and toS[b] != a:
9 return false
10 toT[a] = b; toS[b] = a
11 return true
состояние
toT
{}
toS
–
i
–
a
–
b
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Замена — это правило «буква → буква». Буква s всегда должна превращаться в одну и ту же букву t: toT помнит, во что превратилась каждая.
  2. Две разные буквы s не должны превращаться в одну букву t: toS помнит, откуда взялась каждая буква t. С одним toT пара «stone» → «ladle» прошла бы: n там новая.
  3. Один конфликт в любом словаре — ответ false. Если строки кончились без конфликтов, правило работает в обе стороны: true.

Сложность

Время O(n): один проход, поиск в словаре O(1). Память O(1): в каждом словаре не больше одной записи на букву алфавита, какой бы длины ни были строки.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.