5
\$\begingroup\$

Prompt:

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

I'm a relatively new LeetCoder and I feel pretty good about solving this problem. What are some obvious improvements that I could be making to improve the runtime or approach towards this problem or other problems in general?

public IList<string> LetterCombinations(string digits)
{
    string[] ph = new string[] { "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
    List<string> result = new List<string>();
    if (digits == null || digits.Length == 0) return result;
    int len = ph[digits[0] - '0'].Length;
    for (int i = 0; i < len; i++)
    {
        GetCombos(digits, "", i, ref result, digits.Length);
    }

    return result;
}

public void GetCombos(string inputDigits, string curVariation, int charIndex, ref List<string> resultList, int length)
{
    string[] phone = new string[] { "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    if (curVariation.Length != length)
    {
        char ch = phone[inputDigits[0] - '0'][charIndex];
        curVariation += ch;
    }
    if (curVariation.Length == length)
    {
        resultList.Add(curVariation);
        return;
    }

    string newInput = inputDigits.Substring(1, inputDigits.Length - 1);
    if (newInput == "") return;
    int numChars = phone[newInput[0] - '0'].Length;
    for (int i = 0; i < numChars; i++)
    {
        GetCombos(newInput, curVariation, i, ref resultList, length);
    }
}
\$\endgroup\$
5
\$\begingroup\$

There is only one thing I really don't like:

You have the same array instantiated in two different places (the phone/ph array). Here it's fairly simple and easy to maintain, but IRL you should never do that.

You have two options to resolve this:

1) Create the phone array as a class field or property.

2) In the newest versions of C# you can place the recursive GetCombos(...) as an internal/local function inside LetterCombinations(...) and then only have string[] phone = {...} defined in the outer:

IList<string> LetterCombinations(...)
{
  string[] phone = { ... };

  void GetCombos(...)
  {
    ...
    char ch = phone[inputDigits[0] - '0'][charIndex];
    ...
  }  

  int len = phone[digits[0] - '0'].Length;
  ...
}

As shown the inner function can access the variables defines in the containing method.


Other things:

public void GetCombos(string inputDigits, string curVariation, int charIndex, ref List<string> resultList, int length) { ... }

You don't need the ref keyword because a list is a reference type.


I don't think newInput will ever be empty, so you can skip this check:

  if (newInput == "") return;

I would make this test

  if (digits == null || digits.Length == 0) return result;

as the first thing to do in the method:

  if (string.IsNullOrWhiteSpace(digits)) return new List<string>();

(or maybe throw an exception?)


In GetCombos(...) you could use the yield return concept instead of the resultList argument as shown below:

public IList<string> LetterCombinations(string digits)
{
  if (digits == null || digits.Length == 0) return new List<string>();

  string[] phone = new string[] { "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

  List<string> result = new List<string>();

  IEnumerable<string> GetCombos(string inputDigits, string curVariation, int charIndex, int length)
  {
    if (curVariation.Length != length)
    {
      char ch = phone[inputDigits[0] - '0'][charIndex];
      curVariation += ch;
    }
    if (curVariation.Length == length)
    {
      yield return curVariation;
    }
    else
    {
      string newInput = inputDigits.Substring(1, inputDigits.Length - 1);
      int numChars = phone[newInput[0] - '0'].Length;

      for (int i = 0; i < numChars; i++)
      {
        foreach (string variation in GetCombos(newInput, curVariation, i, length))
        {
          yield return variation;
        }
      }
    }
  }

  int len = phone[digits[0] - '0'].Length;
  for (int i = 0; i < len; i++)
  {
    result.AddRange(GetCombos(digits, "", i, digits.Length));
  }

  return result;
}

The LeetCode challenge states that the return value of LetterCombinations(...) should be IList<string>, but it would be more elegant to let it return IEnumerable<string> as well and then use yield return insted of result.AddRange(GetCombos(...)) (you'll have to make it in a foreach () loop though).


Just for the exercise I made my own version:

IEnumerable<string> LetterCombinations(string digits)
{
  string[] phone = new string[] { "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

  int length = digits.Length;

  IEnumerable<string> Runner(int buttonIndex, int digitIndex)
  {
    if (buttonIndex < 2 || buttonIndex > 9)
      throw new ArgumentOutOfRangeException(nameof(digits));

    if (digitIndex == length)
    {
      foreach (char ch in phone[buttonIndex])
        yield return ch.ToString();
    }
    else
    {
      int newButtonIndex = digits[digitIndex] - '0';
      digitIndex++;

      foreach (char ch in phone[buttonIndex])
      {
        foreach (string tail in Runner(newButtonIndex, digitIndex))
        {
          yield return $"{ch}{tail}";
        }
      }
    }
  }

  return Runner(digits[0] - '0', 1);
}

Not to claim it to be better than yours - in fact it seems to be slightly slower - but just to show another approach.

In fact it can be done in one line using LINQ:

IEnumerable<string> LetterCombinations(string digits)
{
  string[] phone = new string[] { "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
  return digits.Skip(1).Select(d => d - '0').Aggregate(phone[digits[0] - '0'].Select(c => c.ToString()), (acc, i) => phone[i].SelectMany(c => acc.Select(a => $"{a}{c}")));
}
\$\endgroup\$
4
\$\begingroup\$
  1. The methods can be static since they do not access any class instance data.
  2. The ph and phone arrays are used for the same purpose and are created on every call to the method. They should be a single static readonly field. 2a. Remove some boilerplate by using array initializer syntax.
  3. This feels like the perfect place for an iterator function (yield return syntax). 3a. This means eliminating the ref parameter and converting the return types to IEnumerable<string>.
  4. Use string.IsNullOrEmpty() (or string.IsNullOrWhiteSpace()) instead of checking explicitly for null or length zero.
  5. Always wrap if blocks in curly braces, even if it is one statement. Future you will thank yourself if you have to maintain that code.
  6. Give your code a bit of vertical breathing room. It's for programmers to read :)
  7. Very minor nit, but it comes from me being old and living through the bad old days of early .NET frameworks: use string.Empty when you have a "" constant.

Here's what I wind up with as an initial cut:

private static readonly string[] phone = { "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

public static IEnumerable<string> LetterCombinations(string digits)
{
    if (string.IsNullOrWhiteSpace(digits))
    {
        yield break;
    }

    int len = phone[digits[0] - '0'].Length;

    for (int i = 0; i < len; i++)
    {
        foreach (string result in GetCombos(digits, string.Empty, i, digits.Length))
        {
            yield return result;
        }
    }
}

public static IEnumerable<string> GetCombos(string inputDigits, string curVariation, int charIndex, int length)
{
    if (curVariation.Length != length)
    {
        char ch = phone[inputDigits[0] - '0'][charIndex];

        curVariation += ch;
    }

    if (curVariation.Length == length)
    {
        yield return curVariation;
    }

    string newInput = inputDigits.Substring(1, inputDigits.Length - 1);

    if (string.IsNullOrWhiteSpace(newInput))
    {
        yield break;
    }

    int numChars = phone[newInput[0] - '0'].Length;

    for (int i = 0; i < numChars; i++)
    {
        foreach (string result in GetCombos(newInput, curVariation, i, length))
        {
            yield return result;
        }
    }
}
\$\endgroup\$

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.