전화번호와 대기열의 문자 조합

여기서는 큐(BFS) 또는 재귀(DFS)를 사용하여 반복적으로 해결할 수 있는 알고리즘을 세분화하고 단순화하려고 합니다. Javascript에는 모든 배열이 대기열이 될 수 있는 단순성이 있지만 LinkedList도 대기열로 사용할 수 있습니다. 이것이 Java에서 알고리즘이 구현되는 방식입니다.

알고리즘의 빠른 개요는 digits 배열의 모든 숫자를 고려하는 것입니다. '23' 및 각 숫자에 대해 각 키패드( abc 및 def )에 해당하는 문자를 결합하면 다음과 같은 결과가 나타납니다.

ad, ae, af, bd, be, bf, cd, ce, cf.

사진 제공: Charisse Kenion on Unsplash

대기열은 처음에 조합해야 하는 문자( next )를 추적하고 조합 결과를 끝에 저장합니다( next + char ).

이 알고리즘의 가장 어려운 부분은 3개의 중첩된 루프가 있지만 첫 번째는 숫자를 반복하고 두 번째는 대기열에서 보류 중인 모든 조합이 만들어졌는지 확인하고 세 번째는 각 숫자의 문자를 반복한다는 것입니다. 전화 키패드에서.

const letterCombinations = (digits) => {
    if(digits.length === 0) return []

    let queue = []

    queue.push('')

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

    for(let i = 0; i < digits.length; i++){ // digits '23'

        let currQL = queue.length

        while(currQL > 0){ // consider all elements in current queue
            console.log(currQL)
            // stay in the while loop until all pending items in queue have been processed

            console.log(i, queue[0])

            let next = queue.shift()

            console.log('next:', next )

            for(let char of mapping[digits[i]]){ // specific letters on phone number keypad

                console.log('char:', char )

                queue.push(next+char) // concatenate strings

            }
            currQL--

        }
    }
    return queue
};

아이디어/의견이 있는 경우 또는 에서 연락하거나 내portfolio를 확인하세요.