DEV Community

loading...

Letter combinations of phone number with a queue

santispavajeau profile image Santiago Salazar Pavajeau ・2 min read

Here I try to break down and simplify an algorithm that can be solved iteratively with a queue (BFS) or recursively (DFS). Javascript has the simplicity of allowing any array to become a queue, but a LinkedList can also be used as a queue, which is how the algorithm is implemented in Java.

The quick overview of the algorithm is to consider every number in the digits array e.g. '23' and for each number combine the corresponding letters each keypad (abc and def) in this case would result in:

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

phone keypads
Photo by Charisse Kenion on Unsplash

The queue keeps track of the letters we have to combine (next) at the beginning and also stores the result of the combinations at the end (next + char).

The most challenging part of this algorithm is that it has three nested loops, but the first one iterates over the digits, the second one makes sure that all pending combinations in the queue are made, and the third one iterates over the letters of each number in the phone keypads.

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
};
Enter fullscreen mode Exit fullscreen mode

Feel more than welcome to reach out with any ideas/comments at Linkedin or Twitter, or check out my portfolio.

Discussion (0)

pic
Editor guide