## Анаграм

1. [Yandex Contest](https://contest.yandex.ru/contest/8458/problems/E/)

Одна строка является анаграммой другой строки, если из первой можно получить вторую путём перестановки символов

Примеры анаграмм:

* 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 - положить содержимое строк в [ассоциативный массив/словарь](/5%20Swift/5.3%20DataRepresentations/5.3.1%20DataTypes/5.3.1.4%20ValueTypes/5.3.1.4.4%20CollectionsAndTuple/5.3.1.4.4.2%20AssociatedArray.md) и сравнить содержимое массивов для двух строк. Время выполнения алгоритма [линейная](../2.1.2%20ListOfAlgoritms.md), поскольку нам не требую тся дополнительные вычисления в виде сортировки.

```swift
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
}
```

[**Более лаконичное решение**](https://github.com/TerryHuangHD/LeetCode-Swift/blob/master/String/ValidAnagram.swift)

---

[2.1.3 Operators Theme](../2.1.3%20Operators/) | [Back To iTWiki Contents](https://github.com/eldaroid/iTWiki) | [2.1.4.2 Count Chart In String Theme](./2.1.4.2%20CountCharInStr.md)