Leetcode 17. Letter Combinations of a Phone Number

Letter Combinations of a Phone Number.

Just do a BFS on the digits. The number of solution set increases exponentially with the length of the initial digits.

public class Solution {
    string[] map = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public IList<string> LetterCombinations(string digits) {
        Queue<string> res = new Queue<string>();
        for(int i = 0; i < digits.Length; i++){
            int digit = (int)(digits[i] - '0');
            if (i == 0) {
                for(int j = 0; j < map[digit].Length; j++){
                    res.Enqueue(map[digit][j].ToString());
                }
            } else {
                while(res.Peek().Length <= i){
                    string cur = res.Dequeue();
                    for(int j = 0; j < map[digit].Length; j++){
                        res.Enqueue(cur + map[digit][j].ToString());
                    }
                }
            }
        }
        return res.ToList();
    }
}

One Reply to “Leetcode 17. Letter Combinations of a Phone Number”

Leave a Reply

Your email address will not be published. Required fields are marked *