Question

Formatted question description: https://leetcode.ca/all/17.html

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].

Algorithm

Similar topics include Path Sum II, Subsets II, Permutations, Permutations II, Combinations, Combination Sum and Combination Sum II and so on.

Here you can use recursive Recursion to solve, you need to build a dictionary to store the string represented by each number, and then you need a variable level, which records the number of characters in the currently generated string, and realizes the routine and the above questions. similar. In the recursive function, the level is first judged. If the number of digits in digits is equal, the current combination is added to the result res, and then returned. We pass the number in digits to the dict to extract the string, then traverse the extracted string, add each character to the current combination, and call the recursive function.

Code

import java.util.ArrayList;
import java.util.List;

public class Letter_Combinations_of_a_Phone_Number {

	public class Solution {

	    List<String> list = new ArrayList<String>();
	    ArrayList<String> eachDigit = new ArrayList<String>();
	    StringBuilder one = new StringBuilder();

	    public List<String> letterCombinations(String s) {

	        if (s == null)   return list;
	        if (s.length() == 0)    {   list.add("");  return list; }

	        String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; // number 0, 1 is empty string

	        for (int i = 0; i < s.length(); i++) {
	            int num = s.charAt(i) - '0';
	            eachDigit.add(map[num]); // possible out of boundary, assumption is valid input
	        }

	        dfs(eachDigit, 0, s.length());

	        return list;
	    }

	    public void dfs(ArrayList<String> eachDigit, int index, int totalSize) {

	        if (index == totalSize) {
	            list.add(new String(one)); // or, just pass in a result string, and avoid append() then deleteLast()
	            return;
	        }

	        String current = eachDigit.get(index);
	        for (int i = 0; i < current.length(); i++) {
	            one.append(current.charAt(i));
	            dfs(eachDigit, index + 1, totalSize);
	            one.deleteCharAt(one.length() - 1); // if string, then it's s.substring(0, s.length() - 1)
	        }
	    }
	}
}


############

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits.length() == 0) {
            return ans;
        }
        ans.add("");
        String[] d = new String[] {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        for (char i : digits.toCharArray()) {
            String s = d[i - '2'];
            List<String> t = new ArrayList<>();
            for (String a : ans) {
                for (String b : s.split("")) {
                    t.add(a + b);
                }
            }
            ans = t;
        }
        return ans;
    }
}

// OJ: https://leetcode.com/problems/letter-combinations-of-a-phone-number/
// Time: O(4^N)
// Space: O(N)
class Solution {
    vector<string> m{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> ans;
    void dfs(string &digits, int start, string &str) {
        if (start == digits.size()) {
            ans.push_back(str);
            return;
        }
        for (char c : m[digits[start] - '2']) {
            str.push_back(c);
            dfs(digits, start + 1, str);
            str.pop_back();
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        string str;
        dfs(digits, 0, str);
        return ans;
    }
};

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        d = ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
        ans = ['']
        for i in digits:
            s = d[int(i) - 2]
            ans = [a + b for a in ans for b in s]
        return ans

############

class Solution(object):
  def letterCombinations(self, digits):
    """
    :type digits: str
    :rtype: List[str]
    """
    if len(digits) == 0:
      return []

    d = {1: "", 2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz"}

    def dfs(digits, index, path, res, d):
      if index == len(digits):
        res.append("".join(path))
        return

      digit = int(digits[index])
      for c in d.get(digit, []):
        path.append(c)
        dfs(digits, index + 1, path, res, d)
        path.pop()

    res = []
    dfs(digits, 0, [], res, d)
    return res

func letterCombinations(digits string) []string {
	ans := []string{}
	if len(digits) == 0 {
		return ans
	}
	ans = append(ans, "")
	d := []string{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
	for _, i := range digits {
		s := d[i-'2']
		t := []string{}
		for _, a := range ans {
			for _, b := range s {
				t = append(t, a+string(b))
			}
		}
		ans = t
	}
	return ans
}

const map = {
    '2': ['a', 'b', 'c'],
    '3': ['d', 'e', 'f'],
    '4': ['g', 'h', 'i'],
    '5': ['j', 'k', 'l'],
    '6': ['m', 'n', 'o'],
    '7': ['p', 'q', 'r', 's'],
    '8': ['t', 'u', 'v'],
    '9': ['w', 'x', 'y', 'z'],
};

function letterCombinations(digits: string): string[] {
    const n = digits.length;
    if (n === 0) {
        return [];
    }
    const res = [];
    const dfs = (i: number, str: string) => {
        if (i === n) {
            res.push(str);
            return;
        }
        for (const c of map[digits[i]]) {
            dfs(i + 1, str + c);
        }
    };
    dfs(0, '');
    return res;
}

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
    if (digits.length == 0) {
        return [];
    }
    let ans = [''];
    const d = ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
    for (const i of digits) {
        const s = d[parseInt(i) - 2];
        const t = [];
        for (const a of ans) {
            for (const b of s) {
                t.push(a + b);
            }
        }
        ans = t;
    }
    return ans;
};

public class Solution {
    public IList<string> LetterCombinations(string digits) {
        var ans = new List<string>();
        if (digits.Length == 0) {
            return ans;
        }
        ans.Add("");
        string[] d = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        foreach (char i in digits) {
            string s = d[i - '2'];
            var t = new List<string>();
            foreach (string a in ans) {
                foreach (char b in s) {
                    t.Add(a + b);
                }
            }
            ans = t;
        }
        return ans;
    }
}

impl Solution {
    fn dfs(i: usize, digits: &[u8], map: &Vec<Vec<char>>, s: &mut String, res: &mut Vec<String>) {
        if i == digits.len() {
            res.push(s.clone());
            return;
        }
        for c in map[(digits[i] - b'2') as usize].iter() {
            s.push(*c);
            Self::dfs(i + 1, digits, map, s, res);
            s.pop();
        }
    }

    pub fn letter_combinations(digits: String) -> Vec<String> {
        if digits.is_empty() {
            return Vec::new();
        }
        let digits = digits.as_bytes();
        let map = vec![
            vec!['a', 'b', 'c'],
            vec!['d', 'e', 'f'],
            vec!['g', 'h', 'i'],
            vec!['j', 'k', 'l'],
            vec!['m', 'n', 'o'],
            vec!['p', 'q', 'r', 's'],
            vec!['t', 'u', 'v'],
            vec!['w', 'x', 'y', 'z'],
        ];
        let mut res = Vec::new();
        Self::dfs(0, digits, &map, &mut String::new(), &mut res);
        res
    }
}

17 - Letter Combinations of a Phone Number

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions