C# Solution using a feedback loop


  • 0
    J

    This solution utilizes a Divide and Conquer strategy, in that we iteratively build the output step by step, starting from the beginning of the input.

    This produces all combinations in a pre-order traversal fashion.

    One of the downsides of this method is that we are constantly creating and throwing away lists. It should be trivial to modify the getCombinations method to update the passed "current" variable instead of creating a new list each time.

    public class Solution {
        private Dictionary<char, string> keyMap = new Dictionary<char, string> {
            { '0', "" },
            { '1', "" },
            { '2', "abc" },
            { '3', "def" },
            { '4', "ghi" },
            { '5', "jkl" },
            { '6', "mno" },
            { '7', "pqrs" },
            { '8', "tuv" },
            { '9', "wxyz" }
        };
        public IList<string> LetterCombinations(string digits) {
            if (digits == null || digits.Length == 0) {
                return new List<string>();
            }
            List<string> output = new List<string> { "" };
            string currentLetters;
            foreach(char num in digits) {
                currentLetters = keyMap[num];
                output = getCombinations(output, currentLetters);
            }
            return output;
        }
        
        // Return all possible combinations of strings and next letters as a new list
        public List<string> getCombinations(List<string> current, string nextLetters) {
            List<string> ret = new List<string>();
            foreach(string s in current) {
                foreach(char k in nextLetters) {
                    ret.Add(s+k);   
                }
            }
            return ret;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.