Skip to content

17. Letter Combinations of a Phone Number 👍

Approach 1: DFS

  • Time: $O(n4^n)$
  • Space: $O(4^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  vector<string> letterCombinations(string digits) {
    if (digits.empty())
      return {};

    vector<string> ans;

    dfs(digits, 0, "", ans);
    return ans;
  }

 private:
  const vector<string> digitToLetters{"",    "",    "abc",  "def", "ghi",
                                      "jkl", "mno", "pqrs", "tuv", "wxyz"};

  void dfs(const string& digits, int i, string&& path, vector<string>& ans) {
    if (i == digits.length()) {
      ans.push_back(path);
      return;
    }

    for (const char letter : digitToLetters[digits[i] - '0']) {
      path.push_back(letter);
      dfs(digits, i + 1, std::move(path), ans);
      path.pop_back();
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public List<String> letterCombinations(String digits) {
    if (digits.isEmpty())
      return new ArrayList<>();

    List<String> ans = new ArrayList<>();

    dfs(digits, 0, new StringBuilder(), ans);
    return ans;
  }

  private static final String[] digitToLetters = {"",    "",    "abc",  "def", "ghi",
                                                  "jkl", "mno", "pqrs", "tuv", "wxyz"};

  private void dfs(String digits, int i, StringBuilder sb, List<String> ans) {
    if (i == digits.length()) {
      ans.add(sb.toString());
      return;
    }

    for (final char c : digitToLetters[digits.charAt(i) - '0'].toCharArray()) {
      sb.append(c);
      dfs(digits, i + 1, sb, ans);
      sb.deleteCharAt(sb.length() - 1);
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def letterCombinations(self, digits: str) -> list[str]:
    if not digits:
      return []

    digitToLetters = ['', '', 'abc', 'def', 'ghi',
                      'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
    ans = []

    def dfs(i: int, path: list[str]) -> None:
      if i == len(digits):
        ans.append(''.join(path))
        return

      for letter in digitToLetters[int(digits[i])]:
        path.append(letter)
        dfs(i + 1, path)
        path.pop()

    dfs(0, [])
    return ans

Approach 2: Iterative

  • Time: $O(n4^n)$
  • Space: $O(4^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  vector<string> letterCombinations(string digits) {
    if (digits.empty())
      return {};

    vector<string> ans{""};
    const vector<string> digitToLetters{"",    "",    "abc",  "def", "ghi",
                                        "jkl", "mno", "pqrs", "tuv", "wxyz"};

    for (const char d : digits) {
      vector<string> temp;
      for (const string& s : ans)
        for (const char c : digitToLetters[d - '0'])
          temp.push_back(s + c);
      ans = std::move(temp);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public List<String> letterCombinations(String digits) {
    if (digits.isEmpty())
      return new ArrayList<>();

    List<String> ans = new ArrayList<>();
    ans.add("");
    final String[] digitToLetters = {"",    "",    "abc",  "def", "ghi",
                                     "jkl", "mno", "pqrs", "tuv", "wxyz"};

    for (final char d : digits.toCharArray()) {
      List<String> temp = new ArrayList<>();
      for (final String s : ans)
        for (final char c : digitToLetters[d - '0'].toCharArray())
          temp.add(s + c);
      ans = temp;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def letterCombinations(self, digits: str) -> list[str]:
    if not digits:
      return []

    ans = ['']
    digitToLetters = ['', '', 'abc', 'def', 'ghi',
                      'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

    for d in digits:
      temp = []
      for s in ans:
        for c in digitToLetters[int(d)]:
          temp.append(s + c)
      ans = temp

    return ans