Учитывая строку, содержащую только числа 2-9, вернуть все комбинации букв, которые она может представлять. Ответы можно возвращать в любом порядке. Отображение цифр в буквы дается следующим образом (так же, как клавиши телефона). Обратите внимание, что 1 не соответствует ни одной букве.
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
Решение первое
Решайте сами насилие (не рекомендуется), т.к. длина числа в вопросе не превышает 4, поэтому можете обсудить его отдельно.
def letterCombinations1(digits):
n = len(digits)
if n == 0: return []
ans = []
d = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
if n == 1:
for ch in d[digits]:
ans.append(ch)
return ans
if n == 2:
for ch1 in d[digits[0]]:
for ch2 in d[digits[1]]:
ans.append(ch1+ch2)
return ans
if n == 3:
for ch1 in d[digits[0]]:
for ch2 in d[digits[1]]:
for ch3 in d[digits[2]]:
ans.append(ch1+ch2+ch3)
return ans
if n == 4:
for ch1 in d[digits[0]]:
for ch2 in d[digits[1]]:
for ch3 in d[digits[2]]:
for ch4 in d[digits[3]]:
ans.append(ch1+ch2+ch3+ch4)
return ans
Решение второе
отступлениеСсылаясь на избранные ответы Ликоу, когда в вопросе появляются такие слова, как «все комбинации», наше первое чувство — использовать поиск с возвратом.
смысл:Используйте рекурсию, рекурсию сверху вниз для достижения глубокого поиска, определения подзадач и решения исходной проблемы путем объединения результатов подзадач на текущем рекурсивном уровне.
def letterCombinations3(digits):
if not digits: return [] # 如果字符串为空，返回一个空数组
d = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
def backtrack(combination, nextdigit):
"""
递归函数
@param combination: 前面数字的某一个可能字符串组合
@param nextdigit: 剩下的数字
"""
if len(nextdigit) == 0:
# 先写递归出口
# 递归出口，当后面没有数字了的时候，就将这种组合添加到数组里面
res.append(combination)
else:
# 遍历剩下数字中第一个数字对应的字母
for letter in d[nextdigit[0]]:
# 调用递归函数回溯
# 将这个数字的对应的字母letter拼接在组合后面，剩下的数字要除去第一个
backtrack(combination + letter, nextdigit[1:])
res = []
backtrack("", digits) # 调用递归函数，初始的组合为空字符串""，nextdigit为整个数字字符串digits
return res
Решение третье
очередьПрежде чем обратиться к выбранному коду ответа Ликоу, основная идея реализованного вами кода заключается в следующем:Каждый раз он просматривает комбинацию исходного предыдущего числа, а затем просматривает строку, соответствующую новому числу, и объединяет ее последовательно.
def letterCombinations4(digits):
if not digits: return [] # 如果字符串为空，返回一个空数组
d = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
res = [] # 存储结果的数组
for letter in digits:
if len(res) == 0:
# 遍历第一个数字对应的字母
for ch in d[letter]:
res.append(ch)
else:
# 用一个数组存储原来的前面数字所有可能的字母组合
old_res = res.copy()
# 遍历前面数字所有可能的字母组合
for ch1 in old_res:
# 将下一个数字对应的字母都分别加在前面数字所有可能字母组合的后面
for ch2 in d[letter]:
res.append(ch1+ch2)
# 删除原来的前面的字母字母组合
res.remove(ch1)
return res
Способ выбора ответа:Сначала поставьте в очередь каждую букву, соответствующую первой цифре во входных цифрах, затем поставьте в очередь исключенный из очереди элемент, где каждая буква соответствует второй цифре... пока не будет достигнут конец цифр. Последний элемент в очереди — это желаемый результат.
def letterCombinations5(digits):
if not digits: return [] # 如果字符串为空，返回一个空数组
phone = ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
queue = [""] # 初始化队列
for digit in digits:
for _ in range(len(queue)):
tmp = queue.pop(0) # tmp记录当前前面数字的一种字母组合，并删除
# 这里我们不使用 int() 转换字符串，使用ASCII码
# 将数字字符转为ASCII码，50是字符"2"的ASCII码
for letter in phone[ord(digit) - 50]:
queue.append(tmp + letter) # 将tmp加上新的字母，组成组合添加到队列里面
return queue
Анализ сложности
Сложность вышеперечисленных алгоритмов в основном одинакова.
- временная сложность:. M — количество цифр, соответствующих трем буквам во входной числовой строке, а N — количество цифр, соответствующих четырем буквам.
- Сложность пространства:. для создания в общей сложностирезультат.