我目前正在練習(xí)我的面試。我正在研究的問題是獲取電話號碼的所有字母組合。給定一個包含 2-9 位數(shù)字的字符串，返回該數(shù)字可以表示的所有可能的字母組合。下面給出了數(shù)字到字母的映射（就像在電話按鈕上一樣）。請注意，1 不映射到任何字母。是問題所在，數(shù)字-字母對的映射如下所示：nums = { '2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}我對這個問題的解決方案如下：def letterCombinations(self, digits): """ :type digits: str :rtype: List[str] """ letters = {'2':'abc', '3':'def','4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs','8':'tuv', '9':'wxyz'} def backtrack(digits, path, res): if digits == '': res.append(path) return for n in digits: for letter in letters[n]: path += letter backtrack(digits[1:], path, res) path = path[:-1] res = [] backtrack(digits, '', res) return res輸入的正確答案"23"應(yīng)該是["ad","ae","af","bd","be","bf","cd","ce","cf"]但是，我的答案看起來像["ad","ae","af","bd","be","bf","cd","ce","cf","dd","de","df","ed","ee","ef","fd","fe","ff"]在獲得所有所需的組合后，它會不斷獲得具有重疊字母的組合，例如dd de ee等。我不明白為什么會發(fā)生這種情況，因為我只嘗試遍歷每個數(shù)字的可能字母并在此之后終止。是什么導(dǎo)致了這里的錯誤？
3 回答
慕尼黑的夜晚無繁華
TA貢獻(xiàn)1864條經(jīng)驗 獲得超6個贊
我不明白你為什么要這樣做for n in digits:，每次回溯時，你應(yīng)該只關(guān)注當(dāng)前數(shù)字 ( digits[0])，遍歷該數(shù)字的所有可能值，然后將其余工作傳遞給下一個遞歸稱呼。刪除該行并更改n以digits[0]解決您的問題：
def letterCombinations(digits):
"""
:type digits: str
:rtype: List[str]
"""
letters = {'2':'abc', '3':'def','4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs','8':'tuv', '9':'wxyz'}
def backtrack(digits, path, res):
if digits == '':
res.append(path)
return
for letter in letters[digits[0]]:
# note that you can replace this section with
# backtrack(digits[1:], path + letter, res)
path += letter
backtrack(digits[1:], path, res)
path = path[:-1]
res = []
backtrack(digits, '', res)
return res
letterCombinations('23')
輸出：
['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
此外，您應(yīng)該考慮@DYZ 的超級簡潔和令人敬畏的解決方案，它使用itertools：
import itertools
letters = {'2':'abc', '3':'def','4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs','8':'tuv', '9':'wxyz'}
def letterCombinations(digits):
return ["".join(combo) for combo in itertools.product(*[letters[d] for d in digits])]
print(letterCombinations('23'))
輸出：
['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
交互式愛情
TA貢獻(xiàn)1712條經(jīng)驗 獲得超3個贊
讓我們從偽代碼中看一下：
if digits is empty
path is a solution
else
for each letter in current digit
stick the letter on the front of
the letter combos for the rest of the input
這給了我們更短的編程：
def backtrack(digits, path, res):
if len(digits) == 0:
res.append(path)
else:
for letter in letters[digits[0]]:
backtrack(digits[1:], letter + path, res)
蕪湖不蕪
TA貢獻(xiàn)1796條經(jīng)驗 獲得超7個贊
In [34]: def get_prod(number_list):
...: let_list = [nums[i] for i in number_list]
...: r = [[]]
...: for p in let_list:
...: r = [x + [y] for x in r for y in p]
...: return [''.join(i) for i in r]
...:
...:
In [35]: get_prod(['2', '3', '4'])
Out[35]:
['adg',
'adh',
'adi',
'aeg', ...
添加回答
舉報
0/150
提交
取消