Letter Combinations of a Phone Number

Q: 전화번호의 문자 조합 문제의 시간 복잡도는 무엇인가요?

n 개의 숫자에 대해 O(4^n · n) 입니다. 모든 숫자가 7 또는 9일 때 문자열은 4^n개가 될 수 있으며, 각 문자열을 작성하는 데 n 단계가 걸립니다. 이것이 출력의 크기이므로 어떤 해법도 이보다 더 나은 성능을 낼 수 없습니다. 백트래킹은 출력 외에 O(n) 의 추가 공간이 필요합니다.

Q: 백트래킹은 왜 조합을 정렬된 순서로 반환하나요?

모든 답의 길이는 같으며, 깊이 우선 탐색은 a 로 시작하는 모든 문자열을 마친 뒤에 b 를 선택합니다. 각 키의 문자를 왼쪽에서 오른쪽 순서로 시도하는 한, 모든 단계에서 같은 원리가 적용됩니다. 이것이 사전 순서이므로 정렬할 필요가 없습니다.

보통백트래킹

+10

휴대폰 키패드에서는 2부터 9까지 각 숫자에 몇 개의 문자가 할당되어 있습니다. 2는 abc, 3은 def, 4는 ghi, 5는 jkl, 6은 mno, 7은 pqrs, 8은 tuv, 9는 wxyz입니다.

문자열 digits가 주어집니다. 숫자의 순서를 유지하면서 각 숫자에 해당하는 문자 하나씩을 선택하면 키패드로 입력할 수 있는 문자열 하나를 얻습니다. 이러한 문자열을 모두 사전식 순서로 정렬하여 반환하세요.

함수

letterCombinations(digits: string) → string-array

digitsstring: 눌린 숫자 각각은 2부터 9까지입니다
반환값string-array: 키로 입력할 수 있는 모든 문자열을 사전순으로

제약 조건

1 ≤ digits.length ≤ 4
digits의 모든 문자는 2부터 9까지의 숫자입니다.
정답은 최대 4⁴ = 256개의 문자열을 포함합니다.

예제

입력: digits = "23"
출력: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
설명: 2는 a, b, c를 제공하고 3은 d, e, f를 제공합니다. 첫 번째 각 글자는 두 번째 각 글자와 짝을 이룹니다. 첫 번째 글자가 가장 느리게 바뀌도록 정렬하면 문자열은 3 × 3 = 9개입니다.

입력: digits = "94"
출력: ["wg", "wh", "wi", "xg", "xh", "xi", "yg", "yh", "yi", "zg", "zh", "zi"]
설명: 9는 네 글자이고 4는 세 글자이므로, 문자열은 4 × 3 = 12개입니다. w로 시작하는 세 문자열은 모두 x로 시작하는 첫 번째 문자열보다 앞에 옵니다.

후속 질문

사전에 있는 실제 단어인 조합만 원한다고 가정해 봅시다. 먼저 4^n개의 문자열을 모두 만들지 않으려면 어떻게 해야 할까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

정답에는 최대 4^n개의 문자열이 들어가므로, 모든 해법은 문자열을 쓰는 데 최소한 그만큼의 작업을 들입니다. 중요한 것은 모든 선택지를 빠짐없이, 중복 없이 한 번씩 생성하는 것입니다. 이는 각 숫자마다 한 단계가 있고 모든 리프가 정답인 결정 트리를 따라 백트래킹하는 방식입니다.

문자열을 한 번에 한 자리씩 만드세요

핵심 아이디어

빈 문자열 하나를 담은 목록에서 시작해 숫자를 한 번에 하나씩 추가하세요. "23"의 경우 숫자 2는 목록을 a, b, c로 바꾸고, 3은 각각에 d, e, f를 추가해 문자열 아홉 개를 만듭니다.

순서는 정렬된 상태로 유지됩니다. 숫자를 처리하기 전에 목록이 정렬되어 있다면, 그 순서대로 각 접두 문자열을 확장하고 각 접두 문자열에 해당하는 키의 문자를 왼쪽에서 오른쪽으로 추가합니다. 따라서 앞에 있던 접두 문자열은 계속 먼저 나오고, 접두 문자열이 같으면 새 문자의 순서대로 정렬됩니다.

작업량은 결과의 크기에 비례하지만, 한 단계의 목록을 만드는 동안 이전 단계의 목록 전체도 메모리에 남아 있습니다.

알고리즘

combos = [""], 빈 접두사 하나로 시작합니다.
각 숫자에 대해 새 목록을 만듭니다. combos의 각 접두사와 해당 숫자 키의 각 문자를 조합하여 prefix + letter를 추가합니다.
combos를 새 목록으로 바꿉니다.
마지막 숫자까지 처리한 후 combos를 반환합니다.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    combos = [""]  # every prefix built so far; one empty prefix to start
    for digit in digits:
        # Each old prefix grows by each letter of this digit, in order.
        combos = [prefix + letter for prefix in combos for letter in KEYPAD[digit]]
    return combos

결정 트리에서 백트래킹하기

핵심 아이디어

정답은 결정 트리의 잎입니다. 루트는 빈 문자열이고, 각 레벨에서는 다음 숫자에 해당하는 문자를 하나씩 추가합니다. 예를 들어 "23"의 루트에는 a, b, c가 자식으로 있으며, 각각의 자식으로는 d, e, f가 있습니다.

버퍼 하나인 path를 사용해 깊이 우선으로 트리를 탐색합니다. 레벨 i에서 digits[i]에 해당하는 문자 하나를 덧붙여 선택하고, i+1을 대상으로 재귀 호출해 탐색한 다음, 문자를 제거해 되돌립니다. 되돌리기 덕분에 버퍼 하나로 트리 전체를 탐색할 수 있습니다. ad, ae, af를 만든 뒤 문자를 꺼내면 path는 a로 돌아가고, 이어서 빈 문자열이 되어 b를 탐색할 준비를 마칩니다. i가 digits의 끝에 도달하면 복사본을 저장합니다.

시간 복잡도는 여전히 O(4^n · n)이지만, 추가 메모리는 버퍼와 호출 스택으로 O(n)입니다.

알고리즘

빈 path와 빈 result를 유지합니다.
backtrack(i)를 정의합니다. i가 digits의 길이와 같으면 path의 복사본을 저장하고 반환합니다.
그렇지 않으면 digits[i]의 키에 있는 각 문자를 순서대로 처리합니다. 해당 문자를 path에 추가하고, backtrack(i+1)을 호출한 다음, 해당 문자를 제거합니다.
backtrack(0)을 호출하고 result를 반환합니다.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    result = []
    path = []  # the letters chosen so far, one per digit

    def backtrack(i):
        if i == len(digits):
            # Every digit has a letter: this leaf is one finished string.
            result.append("".join(path))
            return
        for letter in KEYPAD[digits[i]]:
            path.append(letter)   # choose
            backtrack(i + 1)      # explore the digits after this one
            path.pop()            # undo, so the next letter can take its place

    backtrack(0)
    return result

함정과 경계 사례

모든 키에 세 글자가 있다고 가정하는 것. 알파벳의 (d-2)*3 인덱스부터 세 글자를 가져오면 7에서 s가 빠지고, 8은 s로 시작합니다. 키패드를 표로 작성하세요.
되돌리기를 잊는 것. path가 계속 길어져서 "23"의 두 번째 답이 ae가 아니라 ade로 나옵니다.
복사본 대신 버퍼를 저장하는 것. Python에서 result.append(path)는 같은 리스트를 아홉 번 저장하고, 마지막에는 리스트가 비어 있습니다.
키의 글자를 오른쪽에서 왼쪽으로 시도하거나, 반복 버전에서 스택의 문자열을 늘리는 것. 둘 다 정렬 순서를 깨뜨립니다.
PHP와 R에서는 "23"이 숫자 23으로 전달될 수 있습니다. 문자를 인덱싱하기 전에 텍스트로 변환하세요.

자주 묻는 질문3

전화번호의 문자 조합 문제의 시간 복잡도는 무엇인가요?

n개의 숫자에 대해 O(4^n · n)입니다. 모든 숫자가 7 또는 9일 때 문자열은 4^n개가 될 수 있으며, 각 문자열을 작성하는 데 n단계가 걸립니다. 이것이 출력의 크기이므로 어떤 해법도 이보다 더 나은 성능을 낼 수 없습니다. 백트래킹은 출력 외에 O(n)의 추가 공간이 필요합니다.

백트래킹은 왜 조합을 정렬된 순서로 반환하나요?

모든 답의 길이는 같으며, 깊이 우선 탐색은 a로 시작하는 모든 문자열을 마친 뒤에 b를 선택합니다. 각 키의 문자를 왼쪽에서 오른쪽 순서로 시도하는 한, 모든 단계에서 같은 원리가 적용됩니다. 이것이 사전 순서이므로 정렬할 필요가 없습니다.

숫자 0과 1은 어떨까요?

전화 키패드에서 0과 1에는 문자가 없으며, 이 버전에서는 2부터 9까지만 사용합니다. 0과 1이 포함될 수 있다면 해당 숫자를 건너뛸지, 아니면 답을 빈 값으로 만들지 결정해야 합니다. 면접에서는 어느 쪽을 원하는지 물어보세요.

def letterCombinations(digits):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

digits = "23"

예상 출력

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]