Anagram

• 똑같은 알파벳으로 이루어진 String을 의미한다.
• LISTEN <-> SILENT

Algorithm

• [abc, cde, bca, ...] 와 같은 list input이 주어졌다고 해보자.
• 첫 번째 Solution으로 생각해보면 각 단어들을 Sorting 후 해당 결과를 Key로 갖는 hash map을 생성하면 된다.

Key	Value
abc	[abc, bca...]
cde	[cde, ...|

• Value들을 1차원 추가해서 return 하면, Answer가 된다.

• 위 방법은 각 단어의 최대 길이를 m이라고 한다면, Sorting 에 의한 O(mlogm), list 원소 개수 만큼의 O(n)이 필요하므로 총 O(nxmlogm) Time Complexity가 필요하고, O(nxm) Space Complexity가 필요하다.

• 두 번째 Solution으로는 O(mlogm)의 Time Complexity를 개선할 수 있다.

• Alphabet을 Counting한 것을 Key로 갖는 것이다.

[aba, cdc, baa]
 a2b1 c2d1 a2b1

• 위 와같은 Input이 있다면 각 알파벳의 갯수를 세기위한 Table을 둬서 Hash map을 구성할 수 있다.

Key	Value
a2b1	[aba, baa, ...]
c2d1	[cdc, ...]

• 이는 O(nxmlogm)이었던 것을 O(nxm)으로 Time Complexity가 개선되었다. 즉, Sorting이 아니라 문자 개수 m만 탐색하면 되는 것으로 대체된 것이다.

---

• 이런 문제는 String과 Hash map의 특성을 이용할줄 알아야 한다.