Problem Statement

Given a digit string, return all possible letter combinations that the number could represent.
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Solution Explanation

Given the input is a number string and we need to find out all the possible string combinations that would be generated if they were dialed on a phone.

We know each digit on a phone dialpad has a associated set of characters, so our algorithm should traverse through the given input string, retrieve associated character string for that digit, add each character to the existing set of result generated.

Initially, we will start with an empty string, push the value to a queue, then append the char associated to each digit.

Below is the code in Java,

    public class PhoneNumberStringCombs {

	public static void main(String[] args) {
		String digits = "9345";
		System.out.println(letterCombinations(digits));

	}

	public static List<String> letterCombinations(String digits) {
		LinkedList<String> list = new LinkedList<>();
		String[] dcm = { "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
		list.add("");
		for (int i = 0; i < digits.length(); i++) {
			String ds = dcm[digits.charAt(i) - '0'];
			while (list.peek().length() == i) {
				String s = list.poll();
				for (int j = 0; j < ds.length(); j++) {
					list.add(s + ds.charAt(j));
				}
			}
		}

		return list;
	}
}

Time Complexity

We traverse through the digit string and for each digit, we get the character string associated append it to the all the values in the queue. So the time complexity is O(n^2).