Одна строка является анаграммой другой строки, если из первой можно получить вторую путём перестановки символов
Примеры анаграмм:
- night - thing;
- cat - act;
- save - vase;
- stressed - desserts;
- aa - a
Примеры: не являющиеся анаграммами:
- save - sale (отличие в буквах v и l);
- save - ave (отсутствие буквы s во втором слове);
- saaa - ssaa (разное количество букв s и a в словах);
Решение:
| № алгоритма | Время | Память | Модификация |
|---|---|---|---|
| 1 | O(n*log(n)) | O(1) | Да |
| 2 | O(n*log(n)) | O(n) | Нет |
| 3 | O(n) | O(n) | Нет |
№1 - отсортировать сроки и потом их сравнить. Мы не тратим дополнительной памяти, но модифицируем входные данные. №2 - скопировать в новые структуры, отсортировать их и сравнить. Тогда мы не модифицируем, но нам понадобится дополнительная память. №3 - положить содержимое строк в ассоциативный массив/словарь и сравнить содержимое массивов для двух строк. Время выполнения алгоритма линейная, поскольку нам не требую тся дополнительные вычисления в виде сортировки.
func isAnagram(_ s: String, _ t: String) -> Bool {
let cortageOfS = s.map { ($0, 1)}
let cortageOfT = t.map { ($0, 1)}
let setOfS = Dictionary(cortageOfS) { key, char in key + 1 }
let setOfT = Dictionary(cortageOfT) { key, char in key + 1 }
return setOfS == setOfT
}2.1.3 Logical Expressions Theme | Back To iOSWiki Contents | 2.1.3.2 Count Chart In String Theme