leetcode with python:17. Letter Combinations of a Phone Numb

题目:

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

给定一数字字串,每一数字都有其可能对应到的字母
求出此数字字串可能对应到的所有字母字串组合
而数字对字母的关係如下:
2:"abc",3:"def",4:"ghi",5:"jkl",6:"mno",7:"pqrs",8:"tuv",9:"wxyz"
ex:input: digits = "23"=>output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

这题我用有点dp(?的感觉下去做

class Solution:    def letterCombinations(self, digits: str) -> List[str]:        ans=[]        d={"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}                def x(s,ans):            r=[]            if ans==[]:                for j in d[s]:                    r.append(j)            else:                for i in range(len(ans)):                    for j in d[s]:                        r.append(ans[i]+j)            return r                for i in digits:            ans=x(i,ans)                    return ans

先设立字典(d)确立数字和字母的对应关係
接着一空阵列ans,和一函数x
此函数需传入一数字字元(i)和阵列(ans)
若阵列为空,则将所有i对应到的字母字元个别放入一空阵列r
结束后回传r
若阵列不为空,则将所有i对应到的字母字元依次加入ans内所有元素尾端后
将改动后的元素放入r,结束后回传r
ex:"23":["a","b","c"]=>["ad","ae","af","bd","be","bf","cd","ce","cf"]
所以我们要做的就是从数字字串第一个字元开始让ans等于x(字元,ans)
不断拓展可能
直到最后一个字元,我们就有数字字串对应到的所有可能字母字串组合了
最后执行时间33ms(faster than 90.56%)

今天比较忙就只更两题啦

那我们下题见