1. Runtime Distribution

2. Submission Details

3. Description

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.

4. Example

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

5. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C" active="active"]

char map[][5] = {
	"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
};

char** letterCombinations(char* digits, int* returnSize) {
	int i = 0, resultLength = 1;

	while (digits[i] != '\0') {
		resultLength *= digits[i] == '7' || digits[i] == '9' ? 4 : 3;
		i++;
	}

	*returnSize = i == 0 ? 0 : resultLength;

	char ** result = (char**)malloc(sizeof(char*) *resultLength);

	for (int j = 0; j < resultLength; j++) {

		result[j] = (char*)malloc(sizeof(char)*i);

		int vary = j, k;

		for (k = 0; k < i; k++) {

			int p = digits[k] == '7' || digits[k] == '9' ? 4 : 3;

			result[j][k] = map[digits[k] - '2'][vary%p];

			vary = vary / p;
		}
		result[j][k] = '\0';
	}
	return result;
}

[/restab]
[restab title="C#"]

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

public IList LetterCombinations(string digits)
{
    if (digits.Length == 0)
    {
        return new List();
    }

    Queue result = new Queue();
    result.Enqueue("");

    for (var i = 0; i < digits.Length; i++)
    {
        var index = digits[i] - '0';
        while (result.Peek().Length == i)
        {
            var prefix = result.Dequeue();
            foreach (var c in Mapping[index])
            {
                result.Enqueue(prefix + c);
            }
        }
    }
    return result.ToList();
}

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C" active="active"]

#include 
#include 

char map[][5] = {
	"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
};

char** letterCombinations(char* digits, int* returnSize) {
	int i = 0, resultLength = 1;

	while (digits[i] != '\0') {
		resultLength *= digits[i] == '7' || digits[i] == '9' ? 4 : 3;
		i++;
	}

	*returnSize = i == 0 ? 0 : resultLength;

	char ** result = (char**)malloc(sizeof(char*) *resultLength);

	for (int j = 0; j < resultLength; j++) {

		result[j] = (char*)malloc(sizeof(char)*i);

		int vary = j, k;

		for (k = 0; k < i; k++) {

			int p = digits[k] == '7' || digits[k] == '9' ? 4 : 3;

			result[j][k] = map[digits[k] - '2'][vary%p];

			vary = vary / p;
		}
		result[j][k] = '\0';
	}
	return result;
}

int main() {
	char digits[3] = {'2','3','\0'};
	int * returnSize = malloc(sizeof(int));
	char ** result = letterCombinations(digits, returnSize);
	printf("%d\n", *returnSize);
	system("pause");
	return 0;
}

[/restab]
[restab title="C#"]

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace Csharp.Queue
{
    [TestClass]
    public class LeetCode0017
    {
        private static readonly string[] Mapping =
        {
            "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
        };

        public IList LetterCombinations(string digits)
        {
            if (digits.Length == 0)
            {
                return new List();
            }

            Queue result = new Queue();
            result.Enqueue("");

            for (var i = 0; i < digits.Length; i++)
            {
                var index = digits[i] - '0';
                while (result.Peek().Length == i)
                {
                    var prefix = result.Dequeue();
                    foreach (var c in Mapping[index])
                    {
                        result.Enqueue(prefix + c);
                    }
                }
            }
            return result.ToList();
        }

        [TestMethod]
        public void Test()
        {
            var digital = "23";
            IList result = LetterCombinations(digital);
            foreach (var str in result)
            {
                Console.WriteLine(str);
            }
        }
    }
}

[/restab]
[/restabs]