17.电话号码的字母组合

链接：17.电话号码的字母组合
难度：Medium
标签：哈希表、字符串、回溯
简介：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

题解 1 - typescript

• 编辑时间：2020-06-12
• 执行用时：64ms
• 内存消耗：32.4MB
• 编程语言：typescript
• 解法介绍：理由哈希表储存值进行递归。

const tel: Record<string, string[]> = {
  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 len = digits.length;
  const ans: string[] = [];
  if (len === 0) return ans;
  const s = digits[0];
  const letters = tel[s];
  const nextLetter = letterCombinations(digits.substr(1));
  if (nextLetter.length === 0) return letters;
  for (const letter of letters) for (const nl of nextLetter) ans.push(letter + nl);
  return ans;
}

题解 2 - typescript

• 编辑时间：2020-08-26
• 执行用时：84ms
• 内存消耗：37.6MB
• 编程语言：typescript
• 解法介绍：深度遍历

const phoneToLetter: Record<string, string> = {
  '2': 'abc',
  '3': 'def',
  '4': 'ghi',
  '5': 'jkl',
  '6': 'mno',
  '7': 'pqrs',
  '8': 'tuv',
  '9': 'wxyz',
};
function letterCombinations(digits: string): string[] {
  const len = digits.length;
  if (len === 0) return [];
  else if (len === 1) return phoneToLetter[digits].split('');
  const arr = phoneToLetter[digits[0]].split('');
  const nextArr = letterCombinations(digits.substr(1));
  const ans = [];
  for (const c of arr) ans.push(...nextArr.map(v => c + v));
  return ans;
}