力扣00017.电话号码的字母组合

发表于 分类于 阅读次数： 本文字数： 2.3k 阅读时长 ≈ 8 分钟
电话号码的字母组合、哈希表、字符串、回溯、中等

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = “23”
输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

示例 2：

输入：digits = “”
输出：[]

示例 3：

输入：digits = “2”
输出：[“a”,”b”,”c”]

提示：

  • 0 <= digits.length <= 4
  • digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

解决方法

C++

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:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) {
            return {};
        }
        vector<string> phone = {
            "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
        };
        vector<string> combinations;
        backtrack(digits, 0, "", combinations, phone);
        return combinations;
    }
private:
    void backtrack(const string& digits, int index, string current, vector<string>& combinations, const vector<string>& phone) {
        if (index == digits.length()) {
            combinations.push_back(current);
            return;
        }
        string letters = phone[digits[index] - '0'];
        for (char letter : letters) {
            current.push_back(letter);
            backtrack(digits, index + 1, current, combinations, phone);
            current.pop_back();
        }
    }
};

结果

执行用时 : 4 ms, 击败 31.65% 使用 C++ 的用户

内存消耗 : 6.75 MB, 击败 75.08% 使用 C++ 的用户

Java

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
class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return combinations;
        }
        String[] phone = {
            "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
        };
        backtrack(digits, 0, new StringBuilder(), combinations, phone);
        return combinations;
    }
    private void backtrack(String digits, int index, StringBuilder current, List<String> combinations, String[] phone) {
        if (index == digits.length()) {
            combinations.add(current.toString());
            return;
        }
        String letters = phone[digits.charAt(index) - '0'];
        for (char letter : letters.toCharArray()) {
            current.append(letter);
            backtrack(digits, index + 1, current, combinations, phone);
            current.deleteCharAt(current.length() - 1);
        }
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Java 的用户

内存消耗 : 40.78 MB, 击败 15.89% 使用 Java 的用户

Python

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
class Solution(object):
    def letterCombinations(self, digits):
        if not digits:
            return []
        phone = {
            '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']
        }
        def backtrack(index, path):
            if index == len(digits):
                combinations.append(''.join(path))
                return
            for letter in phone[digits[index]]:
                path.append(letter)
                backtrack(index + 1, path)
                path.pop()
        combinations = []
        backtrack(0, [])
        return combinations

结果

执行用时 : 20 ms, 击败 40.96% 使用 Python 的用户

内存消耗 : 13.01 MB, 击败 69.30% 使用 Python 的用户

Python3

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
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        phone = {
            '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']
        }
        def backtrack(index, path):
            if index == len(digits):
                combinations.append(''.join(path))
                return
            for letter in phone[digits[index]]:
                path.append(letter)
                backtrack(index + 1, path)
                path.pop()
        combinations = []
        backtrack(0, [])
        return combinations

结果

执行用时 : 36 ms, 击败 89.86% 使用 Python3 的用户

内存消耗 : 16.86 MB, 击败 16.18% 使用 Python3 的用户

C

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
30
31
32
33
34
35
36
37
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char* phone[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
void backtrack(char* digits, int index, char* path, char** combinations, int* count) {
    if (digits[index] == '\0') {
        combinations[*count] = strdup(path);
        (*count)++;
        return;
    }
    int digit = digits[index] - '0';
    char* letters = phone[digit];
    for (int i = 0; i < strlen(letters); i++) {
        path[index] = letters[i];
        backtrack(digits, index + 1, path, combinations, count);
    }
}
char** letterCombinations(char* digits, int* returnSize) {
    if (digits == NULL || *digits == '\0') {
        *returnSize = 0;
        return NULL;
    }
    int len = strlen(digits);
    int total_combinations = 1;
    for (int i = 0; i < len; i++) {
        int digit = digits[i] - '0';
        total_combinations *= strlen(phone[digit]);
    }
    char** combinations = (char**)malloc(total_combinations * sizeof(char*));
    char* path = (char*)malloc((len + 1) * sizeof(char));
    path[len] = '\0';
    int count = 0;
    backtrack(digits, 0, path, combinations, &count);
    free(path);
    *returnSize = count;
    return combinations;
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 C 的用户

内存消耗 : 6.61 MB, 击败 31.77% 使用 C 的用户

C#

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
public class Solution {
    private readonly string[] phone = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };
    public IList<string> LetterCombinations(string digits) {
        IList<string> combinations = new List<string>();
        if (string.IsNullOrEmpty(digits)) {
            return combinations;
        }
        Backtrack(digits, 0, new List<char>(), combinations);
        return combinations;
    }
    private void Backtrack(string digits, int index, List<char> path, IList<string> combinations) {
        if (index == digits.Length) {
            combinations.Add(new string(path.ToArray()));
            return;
        }
        int digit = digits[index] - '0';
        string letters = phone[digit];
        foreach (char letter in letters) {
            path.Add(letter);
            Backtrack(digits, index + 1, path, combinations);
            path.RemoveAt(path.Count - 1);
        }
    }
}

结果

执行用时 : 108 ms, 击败 87.74% 使用 C# 的用户

内存消耗 : 46.07 MB, 击败 5.37% 使用 C# 的用户

JavaScript

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
30
31
32
33
34
/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    if (digits === null || digits.length === 0) {
        return [];
    }
    const phone = {
        '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']
    };
    const combinations = [];
    const backtrack = (index, path) => {
        if (index === digits.length) {
            combinations.push(path.join(''));
            return;
        }
        const letters = phone[digits[index]];
        for (let letter of letters) {
            path.push(letter);
            backtrack(index + 1, path);
            path.pop();
        }
    };
    backtrack(0, []);
    return combinations;
};

结果

执行用时 : 56 ms, 击败 84.24% 使用 JavaScript 的用户

内存消耗 : 47.66 MB, 击败 8.30% 使用 JavaScript 的用户

TypeScript

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
30
function letterCombinations(digits: string): string[] {
    if (!digits || digits.length === 0) {
        return [];
    }
    const phone: { [key: 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']
    };
    const combinations: string[] = [];
    const backtrack = (index: number, path: string[]) => {
        if (index === digits.length) {
            combinations.push(path.join(''));
            return;
        }
        const letters = phone[digits.charAt(index)];
        for (let letter of letters) {
            path.push(letter);
            backtrack(index + 1, path);
            path.pop();
        }
    };
    backtrack(0, []);
    return combinations;
}

结果

执行用时 : 76 ms, 击败 7.96% 使用 TypeScript 的用户

内存消耗 : 50.34 MB, 击败 5.09% 使用 TypeScript 的用户

PHP

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
30
31
32
33
34
35
class Solution {

    /**
     * @param String $digits
     * @return String[]
     */
    function letterCombinations($digits) {
        if ($digits === "") {
            return [];
        }
        $phone = [
            '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 = [];
        $this->backtrack($digits, 0, '', $combinations, $phone);
        return $combinations;
    }
    function backtrack($digits, $index, $path, &$combinations, $phone) {
        if ($index === strlen($digits)) {
            $combinations[] = $path;
            return;
        }
        $letters = $phone[$digits[$index]];
        foreach ($letters as $letter) {
            $this->backtrack($digits, $index + 1, $path . $letter, $combinations, $phone);
        }
    }
}

结果

执行用时 : 12 ms, 击败 18.52% 使用 PHP 的用户

内存消耗 : 19.43 MB, 击败 11.11% 使用 PHP 的用户

Swift

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 {
    let phone: [Character: [Character]] = [
        "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"]
    ]
    func letterCombinations(_ digits: String) -> [String] {
        guard !digits.isEmpty else { return [] }
        var combinations = [String]()
        backtrack(Array(digits), 0, "", &combinations)
        return combinations
    }
    func backtrack(_ digits: [Character], _ index: Int, _ path: String, _ combinations: inout [String]) {
        if index == digits.count {
            combinations.append(path)
            return
        }
        let currentDigit = digits[index]
        guard let letters = phone[currentDigit] else { return }
        for letter in letters {
            backtrack(digits, index + 1, path + String(letter), &combinations)
        }
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Swift 的用户

内存消耗 : 15.64 MB, 击败 15.04% 使用 Swift 的用户

Kotlin

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
30
31
32
class Solution {
    val phone = mapOf(
        '2' to listOf('a', 'b', 'c'),
        '3' to listOf('d', 'e', 'f'),
        '4' to listOf('g', 'h', 'i'),
        '5' to listOf('j', 'k', 'l'),
        '6' to listOf('m', 'n', 'o'),
        '7' to listOf('p', 'q', 'r', 's'),
        '8' to listOf('t', 'u', 'v'),
        '9' to listOf('w', 'x', 'y', 'z')
    )
    fun letterCombinations(digits: String): List<String> {
        if (digits.isEmpty()) {
            return emptyList()
        }
        val combinations = mutableListOf<String>()
        backtrack(digits.toCharArray(), 0, StringBuilder(), combinations)
        return combinations
    }
    private fun backtrack(digits: CharArray, index: Int, path: StringBuilder, combinations: MutableList<String>) {
        if (index == digits.size) {
            combinations.add(path.toString())
            return
        }
        val letters = phone[digits[index]] ?: return
        for (letter in letters) {
            path.append(letter)
            backtrack(digits, index + 1, path, combinations)
            path.deleteCharAt(path.length - 1)
        }
    }
}

结果

执行用时 : 216 ms, 击败 5.45% 使用 Kotlin 的用户

内存消耗 : 37.51 MB, 击败 10.91% 使用 Kotlin 的用户

Dart

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
30
class Solution {
  Map<String, List<String>> phone = {
    '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']
  };
  List<String> letterCombinations(String digits) {
    List<String> combinations = [];
    if (digits.isEmpty) {
      return combinations;
    }
    _backtrack(digits, 0, '', combinations);
    return combinations;
  }
  void _backtrack(String digits, int index, String current, List<String> combinations) {
    if (index == digits.length) {
      combinations.add(current);
      return;
    }
    List<String> letters = phone[digits[index]]!;
    for (var letter in letters) {
      _backtrack(digits, index + 1, current + letter, combinations);
    }
  }
}

结果

执行用时 : 296 ms, 击败 -% 使用 Dart 的用户

内存消耗 : 147.34 MB, 击败 100.00% 使用 Dart 的用户

Go

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
var phone = map[string][]string{
	"2": []string{"a", "b", "c"},
	"3": []string{"d", "e", "f"},
	"4": []string{"g", "h", "i"},
	"5": []string{"j", "k", "l"},
	"6": []string{"m", "n", "o"},
	"7": []string{"p", "q", "r", "s"},
	"8": []string{"t", "u", "v"},
	"9": []string{"w", "x", "y", "z"},
}
func letterCombinations(digits string) []string {
	var combinations []string
	if digits == "" {
		return combinations
	}
	var backtrack func(index int, path string)
	backtrack = func(index int, path string) {
		if index == len(digits) {
			combinations = append(combinations, path)
			return
		}
		letters := phone[string(digits[index])]
		for _, letter := range letters {
			backtrack(index+1, path+letter)
		}
	}
	backtrack(0, "")
	return combinations
}

结果

执行用时 : 4 ms, 击败 9.81% 使用 Go 的用户

内存消耗 : 1.94 MB, 击败 39.95% 使用 Go 的用户

Ruby

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
# @param {String} digits
# @return {String[]}
PHONE = {
  '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']
}
def letter_combinations(digits)
  return [] if digits.empty?
  combinations = []
  backtrack(digits, 0, '', combinations)
  combinations
end
def backtrack(digits, index, path, combinations)
  if index == digits.length
    combinations << path
    return
  end
  letters = PHONE[digits[index]]
  letters.each do |letter|
    backtrack(digits, index + 1, path + letter, combinations)
  end
end

结果

执行用时 : 76 ms, 击败 25.00% 使用 Ruby 的用户

内存消耗 : 206.65 MB, 击败 25.00% 使用 Ruby 的用户

Scala

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
object Solution {
  val phone = Map(
    '2' -> List("a", "b", "c"),
    '3' -> List("d", "e", "f"),
    '4' -> List("g", "h", "i"),
    '5' -> List("j", "k", "l"),
    '6' -> List("m", "n", "o"),
    '7' -> List("p", "q", "r", "s"),
    '8' -> List("t", "u", "v"),
    '9' -> List("w", "x", "y", "z")
  )
  def letterCombinations(digits: String): List[String] = {
    if (digits.isEmpty) {
      return List()
    }
    var combinations = List[String]()
    def backtrack(index: Int, path: String): Unit = {
      if (index == digits.length) {
        combinations = path :: combinations
        return
      }
      val letters = phone(digits(index))
      letters.foreach(letter => backtrack(index + 1, path + letter))
    }
    backtrack(0, "")
    combinations.reverse
  }
}

结果

执行用时 : 452 ms, 击败 100.00% 使用 Scala 的用户

内存消耗 : 53.96 MB, 击败 100.00% 使用 Scala 的用户

Rust

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
30
31
32
33
impl Solution {
    pub fn letter_combinations(digits: String) -> Vec<String> {
        let phone = [
            ('2', "abc"),
            ('3', "def"),
            ('4', "ghi"),
            ('5', "jkl"),
            ('6', "mno"),
            ('7', "pqrs"),
            ('8', "tuv"),
            ('9', "wxyz"),
        ]
        .iter()
        .cloned()
        .collect::<std::collections::HashMap<_, _>>();
        if digits.is_empty() {
            return vec![];
        }
        let mut result = vec!["".to_string()];
        for digit in digits.chars() {
            if let Some(letters) = phone.get(&digit) {
                let mut temp = Vec::new();
                for letter in letters.chars() {
                    for item in &result {
                        temp.push(item.clone() + &letter.to_string());
                    }
                }
                result = temp;
            }
        }
        result
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.14 MB, 击败 26.85% 使用 Rust 的用户

Racket

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
(define letter-map
  #hash((#\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))))
(define (get-letters n)
  (hash-ref letter-map n))
(define/contract (letter-combinations digits)
  (-> string? (listof string?))
  (if (= 0 (string-length digits))
      '()
      (map list->string
           (char-combinations (string->list digits)))))
(define/contract (char-combinations ns)
  (-> (listof char?) (listof (listof char?)))
  (if (null? ns)
      '(())
      (for*/list ([rest-combinations (char-combinations (cdr ns))]
                  [current-letter (get-letters (car ns))])
        (cons current-letter rest-combinations))))

结果

执行用时 : 184 ms, 击败 100.00% 使用 Racket 的用户

内存消耗 : 98.10 MB, 击败 -% 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户