018 두 문자열이 애너그램인지 검사

같은 문자들을 서로 다른 순서로 포함하는 두 문자열을 애너그램(anagram)이라 부른다. 어떤 정의에서는 대소문자를 구분하지 않고(않거나) 여백(공백)을 무시한다.

따라서 어떤 알고리즘을 적용하든 해법은 주어진 문자열을 소문자로 바꾸고 여백(공백)을 제거해야 한다. 첫 번째로 살펴볼 해법에서는 배열을 Arrays.sort()로 정렬한 후 Arrays.equals()로 동등하지 검사한다.

애너그램이면 정렬 후에 서로 동등하다(다음 그림은 두 단어가 애너그램임을 보여준다).

▲ 그림 1-2

위 해법(과 자바 8 함수형 스타일 버전)은 이 책의 예제 코드에 들어 있다. 두 해법의 가장 큰 문제는 정렬 부분이다. 이어지는 해법에서는 정렬 단계를 없애고 (0으로 초기화한) 인덱스 256개의 빈 배열을 사용한다(256개 인덱스는 확장 아스키표의 문자 코드로서 자세한 내용은 002. 반복되지 않는 첫 번째 문자 찾기 절을 참고한다).

알고리즘은 아주 간단하다.