Question

17. Letter Combinations of a Phone Number

中文文档

Description

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'] .

Solutions

Solution 1: Traversal

First, we use an array or hash table to store the letters corresponding to each digit. Then we traverse each digit, combine its corresponding letters with the previous results to get the new results.

The time complexity is $O(4^n)$, and the space complexity is $O(4^n)$. Here, $n$ is the length of the input digits.

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 {
  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;
  }
}

class Solution {
public:
  vector<string> letterCombinations(string digits) {
    if (digits.empty()) {
      return {};
    }
    vector<string> d = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> ans = {""};
    for (auto& i : digits) {
      string s = d[i - '2'];
      vector<string> t;
      for (auto& a : ans) {
        for (auto& b : s) {
          t.push_back(a + b);
        }
      }
      ans = move(t);
    }
    return ans;
  }
};

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
}

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

impl Solution {
  pub fn letter_combinations(digits: String) -> Vec<String> {
    let mut ans: Vec<String> = Vec::new();
    if digits.is_empty() {
      return ans;
    }
    ans.push("".to_string());
    let d = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    for i in digits.chars() {
      let s = &d[((i as u8) - b'2') as usize];
      let mut t: Vec<String> = Vec::new();
      for a in &ans {
        for b in s.chars() {
          t.push(format!("{}{}", a, b));
        }
      }
      ans = t;
    }
    ans
  }
}

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  if (digits.length == 0) {
    return [];
  }
  const 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.splice(0, ans.length, ...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;
  }
}

Solution 2: DFS

We can use the method of depth-first search to enumerate all possible letter combinations. Suppose that a part of the letter combination has been generated, but some digits have not been exhausted. At this time, we take out the letters corresponding to the next digit, and then enumerate each letter corresponding to this digit one by one, add them to the letter combination that has been generated before, to form all possible combinations.

The time complexity is $O(4^n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the input digits.

class Solution:
  def letterCombinations(self, digits: str) -> List[str]:
    def dfs(i: int):
      if i >= len(digits):
        ans.append("".join(t))
        return
      for c in d[int(digits[i]) - 2]:
        t.append(c)
        dfs(i + 1)
        t.pop()

    if not digits:
      return []
    d = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    ans = []
    t = []
    dfs(0)
    return ans

class Solution {
  private final String[] d = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
  private String digits;
  private List<String> ans = new ArrayList<>();
  private StringBuilder t = new StringBuilder();

  public List<String> letterCombinations(String digits) {
    if (digits.length() == 0) {
      return ans;
    }
    this.digits = digits;
    dfs(0);
    return ans;
  }

  private void dfs(int i) {
    if (i >= digits.length()) {
      ans.add(t.toString());
      return;
    }
    String s = d[digits.charAt(i) - '2'];
    for (char c : s.toCharArray()) {
      t.append(c);
      dfs(i + 1);
      t.deleteCharAt(t.length() - 1);
    }
  }
}

class Solution {
public:
  vector<string> letterCombinations(string digits) {
    if (digits.empty()) {
      return {};
    }
    vector<string> d = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> ans;
    string t;
    function<void(int)> dfs = [&](int i) {
      if (i >= digits.size()) {
        ans.push_back(t);
        return;
      }
      for (auto& c : d[digits[i] - '2']) {
        t.push_back(c);
        dfs(i + 1);
        t.pop_back();
      }
    };
    dfs(0);
    return ans;
  }
};

func letterCombinations(digits string) (ans []string) {
  d := []string{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
  t := []rune{}
  var dfs func(int)
  dfs = func(i int) {
    if i >= len(digits) {
      ans = append(ans, string(t))
      return
    }
    for _, c := range d[digits[i]-'2'] {
      t = append(t, c)
      dfs(i + 1)
      t = t[:len(t)-1]
    }
  }
  if len(digits) == 0 {
    return
  }
  dfs(0)
  return
}

function letterCombinations(digits: string): string[] {
  if (digits.length == 0) {
    return [];
  }
  const ans: string[] = [];
  const t: string[] = [];
  const d = ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
  const dfs = (i: number) => {
    if (i >= digits.length) {
      ans.push(t.join(''));
      return;
    }
    const s = d[parseInt(digits[i]) - 2];
    for (const c of s) {
      t.push(c);
      dfs(i + 1);
      t.pop();
    }
  };
  dfs(0);
  return ans;
}

impl Solution {
  pub fn letter_combinations(digits: String) -> Vec<String> {
    let d = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    let mut ans = Vec::new();
    let mut t = String::new();
    if digits.is_empty() {
      return ans;
    }
    Solution::dfs(&digits, &d, &mut t, &mut ans, 0);
    ans
  }

  fn dfs(digits: &String, d: &[&str; 8], t: &mut String, ans: &mut Vec<String>, i: usize) {
    if i >= digits.len() {
      ans.push(t.clone());
      return;
    }
    let s = d[((digits.chars().nth(i).unwrap() as u8) - b'2') as usize];
    for c in s.chars() {
      t.push(c);
      Solution::dfs(digits, d, t, ans, i + 1);
      t.pop();
    }
  }
}

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

public class Solution {
  private readonly string[] d = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
  private string digits;
  private List<string> ans = new List<string>();
  private System.Text.StringBuilder t = new System.Text.StringBuilder();

  public IList<string> LetterCombinations(string digits) {
    if (digits.Length == 0) {
      return ans;
    }
    this.digits = digits;
    Dfs(0);
    return ans;
  }

  private void Dfs(int i) {
    if (i >= digits.Length) {
      ans.Add(t.ToString());
      return;
    }
    string s = d[digits[i] - '2'];
    foreach (char c in s) {
      t.Append(c);
      Dfs(i + 1);
      t.Remove(t.Length - 1, 1);
    }
  }
}

class Solution {
  /**
   * @param string $digits
   * @return string[]
   */

  function letterCombinations($digits) {
    $digitMap = [
      '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'],
    ];

    $combinations = [];

    backtrack($digits, '', 0, $digitMap, $combinations);

    return $combinations;
  }

  function backtrack($digits, $current, $index, $digitMap, &$combinations) {
    if ($index === strlen($digits)) {
      if ($current !== '') {
        $combinations[] = $current;
      }
      return;
    }

    $digit = $digits[$index];
    $letters = $digitMap[$digit];

    foreach ($letters as $letter) {
      backtrack($digits, $current . $letter, $index + 1, $digitMap, $combinations);
    }
  }
}