[Reet code] 17. Letter Combinations of a Phone Number

details

Intuition

주어진 문자열이 가질 수 있는 알파벳을 조합한다. 재귀함수를 이용하여 문자열의 길이를 줄여나가고, 알파벳을 조합한다.베이스 케이스로, 문자열을 길이가 0이 되면 함수를 종료한다.

Approach

재귀함수를 사용한다. disits 을 줄이고, disit 에 맞는 문자열을 반복문으로 순회하며 알바펫을 조합한다. 베이스케이스에 도달하면 결과에 추가하고, 이전 함수 콜백으로 돌아가서 다음 반복문을 수행한다.

Complexity

• Time complexity: O(M^N)
  문자열의 길이 2~9 로 8개 숫자당 가지는 알파벳의 수가 평균 3개이므로 최대 3^8 의 경우의 수를 갖는다.

• Space complexity: O(N)

Code

const phone = {
    2: ["a", "b", "c"],
    3: ["d", "e", "f"],
    4: ["g", "h", "i"],
    5: ["j", "k", "l"],
    6: ["m", "n", "o"],
    7: ["p", "q", "r", "s"],
    8: ["t", "u", "v"],
    9: ["w", "x", "y", "z"]
}

function letterCombinations(digits: string): string[] {
    const result = []
    const getCombine = (str: string, digits: string) => {
        if (digits.length === 0) {
            result.push(str)
            return
        }
        for (const alpha of phone[digits[0]]) {
            getCombine(str + alpha, digits.slice(1))
        }
    }

    if (digits === "") {
        return []
    }
    
    getCombine("", digits)
    return result
};