func letterCombinations(digits string) []string {
digmap:=map[int]string{1:"",
2:"abc",
3:"def",
4:"ghi",
5:"jkl",
6:"mno",
7:"pqrs",
8:"tuv",
9:"wxyz",
0:" "}
strs:=make([]string,0)
for i:=0;i<len(digits);i++{
strs=append(strs, digmap[int(digits[i]-'0')])
}
return dp(strs)
}
func dp(strs[]string)[]string{
if len(strs)==0{
return make([]string,0)
}
if len(strs)==1{
ret:=make([]string,0)
for i:=0;i<len(strs[0]);i++{
ret=append(ret,string(strs[0][i]))
}
return ret
}
dpstr:=dp(strs[1:])
ret:=make([]string,0)
for i:=0;i<len(strs[0]);i++{
for j:=0;j<len(dpstr);j++{
ret=append(ret,string(strs[0][i])+dpstr[j])
}
}
return ret
}