Finding Possible Strings from Series of Numbers

Question

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 is done just like they are arranged on a telephone keypad.

Looking for ways of making the code more consise and easily readable. Want to learn the C# tricks to make solving or implementing this solution easier.

using System;
using System.Collections.Generic;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            LetterCombinations("34");
        }
        public static void LetterCombinations(String number)
        {
            string[][] StringMapping = new string[number.Length][];
            int LengthIndex = 0;

            foreach (char c in number)
            {
                switch (c)
                {
                    case '2':
                        StringMapping[LengthIndex] = new string[] {"a", "b", "c"};
                        break;
                    case '3':
                        StringMapping[LengthIndex] = new string[] {"d", "e", "f"};
                        break;
                    case '4':
                        StringMapping[LengthIndex] = new string[] {"g", "h", "i"};
                        break;
                    case '5':
                        StringMapping[LengthIndex] = new string[] {"j", "k", "l"};
                        break;
                    case '6':
                        StringMapping[LengthIndex] = new string[] {"m", "n", "o"};
                        break;
                    case '7':
                        StringMapping[LengthIndex] = new string[] {"p", "q", "r", "s"};
                        break;
                    case '8':
                        StringMapping[LengthIndex] = new string[] {"t", "u", "v"};
                        break;
                    case '9':
                        StringMapping[LengthIndex] = new string[] {"w", "x", "y", "z"};
                        break;
                }
                LengthIndex++;
            }

            int[] SizeArray = new int[StringMapping.Length];        //Keeps track of the size of each inner String array
            int[] counterArray = new int[StringMapping.Length];     //Keeps track of the index of each inner String array, which will be used to make the next combination

            //Discover the size of each inner array and populate sizeArray.
            //Also calculate the total number of combinations possible using the inner String array sizes.
            int totalCombinationCount = 1;
            for (int i = 0; i < StringMapping.Length; i++)
            {
                SizeArray[i] = StringMapping[i].Length;
                totalCombinationCount *= StringMapping[i].Length;
            }

            //Store the combinations in a List of String objects
            List<String> combinationList = new List<String>(totalCombinationCount);
            String sb = "";

            for (int countdown = totalCombinationCount; countdown > 0; countdown--)
            {
                sb = "";
                for (int i = 0; i < StringMapping.Length; i++)
                {
                    sb += StringMapping[i][counterArray[i]];
                }

                combinationList.Add(sb.ToString());

                //Now we need to increment the counterArray so that the next
                //combination is taken on the next iteration of this loop.
                for (int incIndex = StringMapping.Length - 1; incIndex >= 0; incIndex--)
                {
                    if (counterArray[incIndex] + 1 < SizeArray[incIndex])
                    {
                        ++counterArray[incIndex];
                        break;
                    }
                    counterArray[incIndex] = 0;
                }
            }

            //Output the strings in the list
            foreach (String s in combinationList)
            {
                Console.WriteLine(s);
            }
        }
    }
}

Answer 1

A string implements IEnumerable<char> and has an indexer, so you can iterate it as an array.

You can therefore simplify this:

string[][] StringMapping = new string[number.Length][];
            int LengthIndex = 0;

            foreach (char c in number)
            {
                switch (c)
                {
                    case '2':
                        StringMapping[LengthIndex] = new string[] {"a", "b", "c"};
                 ...

without any other changes to:

string[] StringMapping = new string[number.Length];
            int LengthIndex = 0;

            foreach (char c in number)
            {
                switch (c)
                {
                    case '2':
                        StringMapping[LengthIndex] = "abc";

and your code will work fine.

You could though create a separate method for the mapping as:

private static string GetPattern(char number)
{
  switch (number)
  {
    case '2': return "abc";
    case '3': return "def";
    case '4': return "ghi";
    case '5': return "jkl";
    case '6': return "mno";
    case '7': return "pqrs"; 
    case '8': return "tuv"; 
    case '9': return "wxyz";
    default: throw new InvalidOperationException();
  }
}

So your StringMapping could be initialized as:

string[] stringMapping = number.Select(n => GetPattern(n)).ToArray();

Some would claim that a Dictionary<char, string> would be better instead of the switch statement. In a localized scenario for instance, where you would load the mapping dynamically that would be the solution.

Notice the naming: stringMapping (camelCase) for class fields and local variables instead of StringMapping (PascalCase) that is used for properties and method names.

---

I find SizeArray unnecessary and waste of memory:

  int[] SizeArray = new int[StringMapping.Length];

The only place you are using it is here:

      if (counterArray[incIndex] + 1 < SizeArray[incIndex])

which could be replaces with:

if (counterArray[incIndex] + 1 < stringMapping[incIndex].Length)

---

for (int countdown = totalCombinationCount; countdown > 0; countdown--)

There is nothing wrong with iterating backward if the situation demands it, but at least I have to look an extra time, when I see a backward loop. Here there is no reason for the above backward iteration as you only use it to count combinations, the countdown index isn't used to anything in the loop, so it could run forward without any damage:

for (int countdown = 0; countdown < totalCombinationCount; countdown++)

---

Your algorithm works fine, but the overall impression is that it is more complex than it has to be, and due to the double nested loops it is not very efficient.

FYI: below are some other approaches (they all use the GetPattern() method shown above):

1) An iterative version that uses a list to cache all the combinations while creating them:

void LetterCombinationsIter(string numbers)
{
  IEnumerable<string> CreateCombinations()
  {
    List<string> combs = new List<string> { "" };

    for (int i = 0; i < numbers.Length; i++)
    {
      List<string> temp = new List<string>();
      string chars = GetPattern(numbers[i]);

      foreach (string comb in combs)
      {
        foreach (char ch in chars)
        {
          temp.Add(comb + ch);
        }
      }

      combs = temp;
    }

    return combs;
  }

  Console.WriteLine(string.Join(Environment.NewLine, CreateCombinations()));
}

2) A recursive version which is often the intuitive choice for this kind of problems:

void LetterCombinationsRec(string numbers)
{
  char[] buffer = new char[numbers.Length];

  IEnumerable<string> HandleIndex(int index)
  {
    if (index >= numbers.Length)
    {
      yield return new string(buffer);
    }
    else
    {
      foreach (char ch in GetPattern(numbers[index]))
      {
        buffer[index] = ch;
        foreach (string comb in HandleIndex(index + 1))
        {
          yield return comb;
        }
      }
    }
  }

  Console.WriteLine(string.Join(Environment.NewLine, HandleIndex(0)));
}

3) Finally a version using Linq that solves the problem in a few lines of code:

void LetterCombinationsLinq(string numbers)
{
  IEnumerable<string> CreateCombinations()
  {
    return numbers.Aggregate(new[] { "" }.AsEnumerable(), (combs, n) =>
    {
      string chars = GetPattern(n);
      return combs.SelectMany(pre => chars.Select(ch => pre + ch));
    });
  }

  Console.WriteLine(string.Join(Environment.NewLine, CreateCombinations()));
}