【leetcode系列】【py3】【中等】电话号码的字母组合
题目:
原题链接: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
解题思路:
"所有组合",第一反应就是回溯
但是这个题感觉不需要剪枝,直接往后拼接就好了
所以用DFS把所有可能的字符串都拼接好就行了
我实现的使用了stack来保存当前已拼接好的字符串,用于下一次循环
代码实现:
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
num_len = len(digits)
if 0 == num_len:
return []
num_map = {'2' : 'abc', '3' : 'def', '4' : 'ghi', '5' : 'jkl', '6' : 'mno', '7' : 'pqrs', '8' : 'tuv', '9' : 'wxyz'}
res_lst = [i for i in num_map[digits[0]]]
for curr_num in digits[1:]:
tmp_lst = []
while 0 < len(res_lst):
a = res_lst.pop()
for b in num_map[curr_num]:
tmp_lst.append(a + b)
res_lst = tmp_lst
return res_lst
再来一个为什么用py来做题,不用c++做题的理由(虽然这么做和题目原本的意思相差较远):
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
conversion={'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
if len(digits)==0:
return []
product=['']
for k in digits:
product=[i+j for i in product for j in conversion[k]]
return product作者:jutraman
链接:https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/pythondian-hua-hao-ma-de-zi-mu-zu-he-by-jutraman/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。