图解电话号码的字母组合的DFS、BFS两种解法

整体思路

题目链接
本题的真实场景是解析用户打字的各可能组合
时间复杂度:最坏的情况下每次需要遍历4次,O(4n)O(4^n),n为数字串的长度。
空间复杂度:O(n)O(n),递归栈调用的深度。

解空间解空间

感谢leetcode用户笨猪爆破组的解析图。

回溯本质是暴力搜索,如果要找出所有的解,则要搜索整个子树,如果找出一个解则进行回溯。

类似找出所有可能的组合的问题,适合回溯算法。

回溯类题目,有三个关键点:

  • 选择
    决定了你每个节点有哪些分支,可以帮助你构建出解的空间树。
  • 约束条件
    用来剪枝,剪去不满足约束条件的子树,避免无效的搜索。
  • 目标
    决定了何时捕获解,或者剪去得不到解的子树,提前回溯。

DFS解法

def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        #定义数字和字母的映射
        phone_map_dict = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
        result_list=[]
        def dfs(current_str, index:int):
            #结束条件
            if index == len(digits):
                result_list.append(current_str)
                return
            letters = phone_map_dict[digits[index]]
            for c in letters:
                dfs(current_str + c, index + 1)
        
        dfs('', 0)
        #递归遍历所有组合
        return result_list

BFS解法

def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        #定义数字和字母的映射
        phone_map_dict = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
        q= queue.Queue() 
        q.put('');
        for i in range(len(digits)):    # bfs的层数,即digits的长度
            node_num = q.qsize()        # 当前层的节点个数
            for j in range(node_num):   # 逐个让当前层的节点出列
                current_str = q.get()   # 出列
                letters = phone_map_dict[digits[i]]      
                for l in letters:
                    q.put(current_str+l)
        return list(q.queue)