7
\$\begingroup\$

Problem statement (online source)

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input: Digit string "23"

Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

I have seen and read the reviews for the above problem, and made the modifications suggested. I did see the comment on using LINQ, I am learning how to use them and don't fully understand it yet. I successfully submitted my answer to LeetCode, but I would like a review to see what else I can do to improve the code. I noticed the code uses more memory than most submissions on LeetCode and I wonder if I can find out why here.

My code is based on a tutorial I watched. While it was in Java, I typed my code in C#. It recursively calls the method that looks into the objects of a Dictionary and concatenates the data inside them in the desired format. I am new to programming so I looked up stuff online and made some assumptions on equivalent data structures in C#. For example, the original code used a HashMap, and saw a recommendation online to used Dictionary<T, T> in C#.

public class Solution {
public IList<string> LetterCombinations(string digits) {
    List<String> result = new List<String>();
    if (String.IsNullOrEmpty(digits)){
        return result;
        throw new ArgumentNullException(nameof(digits));
    }
    Dictionary<Char, Char[]> lettersMap = new Dictionary<Char, char[]>();
        lettersMap.Add('1', null);
        lettersMap.Add('2', new[] { 'a', 'b', 'c' });
        lettersMap.Add('3', new[] { 'd', 'e', 'f' });
        lettersMap.Add('4', new[] { 'g', 'h', 'i' });
        lettersMap.Add('5', new[] { 'j', 'k', 'l' });
        lettersMap.Add('6', new[] { 'm', 'n', 'o' });
        lettersMap.Add('7', new[] { 'p', 'q', 'r', 's' });
        lettersMap.Add('8', new[] { 't', 'u', 'v' });
        lettersMap.Add('9', new[] { 'w', 'x', 'y', 'z' });
        lettersMap.Add('0', null);
        StringBuilder sb = new StringBuilder();
        int pos = 0;
        LetterCombinationsFunction(digits, sb, lettersMap, result, pos);
    return result;
}
private static List<String> LetterCombinationsFunction(String digits, StringBuilder sb,
                Dictionary<Char, Char[]> lettersMap, List<String> result, int pos)
    { 
        if (sb.Length == digits.Count())
        {
            result.Add(sb.ToString());
            return result;
        }
        lettersMap.TryGetValue(digits[pos], out char[] values);        
            foreach (var v in values)
            {  
                sb.Append(v);
                LetterCombinationsFunction(digits, sb, lettersMap, result, pos+1);
                sb.Remove(sb.Length - 1, 1);
            }      
        return result;
    }
}
\$\endgroup\$
7
\$\begingroup\$

I have a few other minor thoughts, but the big one is: rather than building the lookup dictionary on each call, since it's the same static and read-only data, presumably forever, make it a class-level member and don't pass it around:

    private static readonly IReadOnlyDictionary<char, char[]> _LettersMap = new Dictionary<char, char[]>
    {
        { '1', null },
        { '2', new[] { 'a', 'b', 'c' } },
        { '3', new[] { 'd', 'e', 'f' } },
        { '4', new[] { 'g', 'h', 'i' } },
        { '5', new[] { 'j', 'k', 'l' } },
        { '6', new[] { 'm', 'n', 'o' } },
        { '7', new[] { 'p', 'q', 'r', 's' } },
        { '8', new[] { 't', 'u', 'v' } },
        { '9', new[] { 'w', 'x', 'y', 'z' } },
        { '0', null }
    };
\$\endgroup\$
  • \$\begingroup\$ C Slicer-Thanks. I'll make the change. This is a great idea. \$\endgroup\$ – Saaman Oct 1 at 17:48
7
\$\begingroup\$

Review

  • LetterCombinations returns an IList<string> but I see no reason to return a modifiable collection. Consider returning IEnumerable<string> instead.
  • A method's name should be a verb. Change LetterCombinations to GetLetterCombinations, FindLetterCombinations or PermutateLetterCombinations.
  • You did good by creating a private function that performs the recursion with intermediate parameters. This way, the user of this API only needs to think about the public endpoint. However, it could have used the same name as the public method. An overload would not resulted in a conflict. The postfix *Function is weird.
  • Prefer the use of var if the type can be read from code: var lettersMap = new Dictionary<char, char[]>();
  • You are looking to get familiar with LINQ, however the next statement did not require the LINQ wrapper Count() of a string's Length property: if (sb.Length == digits.Count()).
  • Use more consistent indentation for your class members.
  • Having the opening curly brace on the same line is ok, but it's more a convention in Java than in C#, where the opening curly brace is usually on the next line.
  • See Jesse C. Slicer's answer to move the static data out of the method.

Peculiarities

Did you plan to return the empty result list or throw an exception on this edge case?

if (String.IsNullOrEmpty(digits)){
    return result;
    throw new ArgumentNullException(nameof(digits));
}

The next line is followed by a loop over values but doesn't care whether the operation succeeded:

lettersMap.TryGetValue(digits[pos], out char[] values);

Did you plan to write this instead?

if (lettersMap.TryGetValue(digits[pos], out char[] values)) 
{
    // ..
}

You are using both char and Char in the next line. Is there a specific reason to use both these types?

Dictionary<Char, Char[]> lettersMap = new Dictionary<Char, char[]>();
\$\endgroup\$
  • 1
    \$\begingroup\$ dfhwze-Thanks. I meant to use Char; I'll change the other instances. re: Exception vs. empty result, I'll remove the empty result. I did see a comment on adding {}'s to if statements, and missed this one. I'll add it. I need to understand IEnumerables much better. I can use them, and in this instance it seems passing one IEnumerable object instead of an entire collection would save me memory space especially once I make the change Jesse C. Slicer mentioned also. I also need to really understand how yield works, beyond the example of MSN docs that is, and how it is used instead of IEnumerable. \$\endgroup\$ – Saaman Oct 1 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.