Word Pattern

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

Даны шаблон из букв и строка из слов через пробел. Нужно понять, подходит ли строка под шаблон: каждая буква всегда обозначает одно и то же слово, а две разные буквы не обозначают одно слово. Наш пример: шаблон «abab» и «tick tock tick tock» — да, a — это tick, b — tock.

290 Word PatternРазбор · 1×

Пример: шаблон «abab», строка «tick tock tick tock». Под ними оба словаря: буква → слово и слово → буква.

pattern0a1b2a3bwordsticktockticktocktoWordp → w—toLetterw → p—
ещё не дошлитекущая парапровереноконфликтподходит под шаблон

Делим строку по пробелам: 4 слова

01/25
сначала · назад · пуск · шаг
Скорость
1function wordPattern(pattern, s):
2 words = split s at spaces
3 if len(words) != len(pattern):
4 return false
5 toWord = empty map
6 toLetter = empty map
7 for i from 0 to len(pattern) - 1:
8 p = pattern[i]; w = words[i]
9 if p in toWord and toWord[p] != w:
10 return false
11 if w in toLetter and toLetter[w] != p:
12 return false
13 toWord[p] = w; toLetter[w] = p
14 return true
состояние
words
[tick, tock, tick, tock]
toWord
–
toLetter
–
i
–
p
–
w
–
историянажмите шаг, чтобы вернуться

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

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

  1. Это проверка из Isomorphic Strings, только буква обозначает целое слово: toWord хранит «буква → слово», toLetter — «слово → буква».
  2. Если букв и слов разное количество, совпасть они не могут, поэтому это проверяем первым, до словарей.
  3. Один конфликт в любом словаре — ответ false. Без конфликтов до конца каждая буква всегда встречает одно слово и наоборот: true.

Сложность

Время O(n), n — длина строки: разбить её на слова и пройти по ним один раз. Память O(n): слова и два словаря.

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

Решить на LeetCode ↗

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