Letter Combinations of a Phone Number

답을 한 번에 한 자리씩 만드세요. 빈 문자열 하나를 담은 목록으로 시작합니다. "23"의 경우, 숫자 2는 이를 a, b, c로 바꿉니다. 그런 다음 숫자 3은 이 세 문자열 각각에 d, e, f를 붙여 길이가 2인 문자열 아홉 개를 만듭니다. 마지막 숫자를 처리한 뒤에는 목록에 모든 답이 담깁니다.

결과는 별도의 작업 없이 정렬된 순서로 나옵니다. 숫자를 처리하기 전의 목록이 정렬되어 있다고 가정해 보세요. 접두사들을 같은 순서로 확장하고, 각 접두사에는 해당 키의 문자를 왼쪽에서 오른쪽 순서로 붙입니다. 앞선 접두사를 가진 문자열이 여전히 먼저 오고, 접두사가 같은 두 문자열은 새 문자에 따라 정렬되는데, 이는 사전순입니다.

비용은 답의 크기만큼 듭니다. 숫자가 n개라면 마지막 목록에는 길이가 n인 문자열이 최대 4^n개 들어가며, 이전 목록 전체에는 이보다 최대 절반 정도의 문자열이 들어가고, 그 문자열은 모두 더 짧습니다. 단점은 메모리입니다. 한 단계의 목록을 만드는 동안 이전 단계의 목록 전체도 메모리에 남아 있으며, 여기에는 버리게 될 짧은 접두사도 모두 포함됩니다.

정답을 의사 결정 트리로 생각해 보세요. 루트는 빈 문자열입니다. "23"에는 자식이 세 개 있으며, 2의 각 문자에 해당하는 a, b, c입니다. 이 자식들은 각각 또 세 개의 자식을 가지며, 3의 각 문자에 하나씩 해당합니다. 트리에는 숫자 하나당 한 레벨이 있고, ad부터 cf까지의 아홉 개 잎 노드가 바로 정답입니다.

백트래킹은 하나의 버퍼 path를 사용해 트리를 깊이 우선으로 순회합니다. 레벨 i에서는 digits[i]의 문자를 하나 선택해 추가하고, i+1을 재귀 호출해 그 아래의 모든 경우를 탐색한 다음, 문자를 제거해 선택을 되돌립니다. 선택을 되돌리기 때문에 버퍼 하나로 트리 전체를 처리할 수 있습니다. ad, ae, af를 저장한 뒤 문자를 꺼내면 path는 a로 돌아가고, 이어서 빈 문자열로 돌아가 b를 처리할 준비가 됩니다. i가 digits의 길이와 같아지면 버퍼는 완성된 정답이므로, 복사본을 저장합니다.

각 레벨에서 왼쪽부터 문자를 시도하면 잎 노드를 사전 순서로 방문하므로 결과를 정렬할 필요가 없습니다. 이 문제에서는 모든 분기가 정답으로 끝나므로 가지치기할 부분이 없습니다. 트리는 깊이가 4에 불과하고 잎 노드는 최대 256개입니다. 정답을 쓰는 데 드는 작업량은 여전히 O(4^n · n)이지만, 추가 메모리는 전체 접두사 레벨이 아니라 버퍼와 호출 스택에 사용하는 O(n)입니다. 같은 선택, 탐색, 되돌리기 반복문으로 부분 집합, 순열, 조합 합, 단어 찾기 문제도 해결할 수 있습니다.