本文共 1105 字,大约阅读时间需要 3 分钟。
Given a string containing digits from 2-9
inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:
Input: "23"Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
其实就是把所有字母组合输出一遍。
首先建立一个字典,通过input的数字,比如“23”,获得对应的字符串['abc', 'def']。
然后就是组合过程,我用的BFS方法。
bfs存储的是到当前的字符串所有的字母组合。
最开始是 ['']
与‘abc’组合后是 ['a', 'b', 'c']与‘def’组合后是 ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
letters就是新的字符串比如’def'
class Solution: def letterCombinations(self, digits: str) -> List[str]: if len(digits)==0:return [] mapping = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'} lis=[] for digit in digits: lis.append(mapping[digit]) bfs=[''] for letters in lis: temp=[] for b in bfs: for letter in letters: temp.append(b+letter) bfs=temp return bfs
转载地址:http://ncrbb.baihongyu.com/