山东高端网站设计,win2003 建设网站,网站建设后台管理怎么管理,怎么判断是不是外包公司17.给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下#xff08;与电话按键相同#xff09;。注意 1 不对应任何字母。 示例 1#xff1a; 输入#xff1a;digits “23” 输出#xff1a;[… 17.给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 1 输入digits “23” 输出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”] 示例 2 输入digits “” 输出[] 示例 3 输入digits “2” 输出[“a”,“b”,“c”] 首先我们根据每个按键对应的字母先创建一个二维字符数组 tab。分析题目每个按键对应几个字符那么当我们组合时比如示例 1“2” 对应的字符为 [a,b,c]即我们在组合时首位可以为这三种可能在这三种可能的基础上我们继续延伸3 对应为 def即我们从之前的三种可能可以再分别延伸出三种可能比如最开始选 a就能得到 [ad,ae,af]最开始选 b 就能得到 [bd,be,bf]…。我们可以发现这样从一种可能延伸出其他可能就像是一棵 n 叉树只不过根节点的值为空字符。那么我们就 bfs 这棵树得到所有可能。我们用一个 list 从尾部存储结果取的时候从头取。如果头部的拼接字符串已经等于 digits 的长度了说明每种可能都拼接完毕。可以代入例子 1 分析以下代码res 的变化会经历 [] - [a,b,c] - [b,c,ad,ae,af] - [c,ad,ae,af,bd,be,bf] - [ad,ae,af,bd,be,bf,cd,ce,cf] public ListString letterCombinations(String digits) {LinkedListString res new LinkedList();//空判断if (digits null || digits.isEmpty())return res;// 按键对应表char[][] tab {{a, b, c}, {d, e, f}, {g, h, i},{j, k, l}, {m, n, o}, {p, q, r, s},{t, u, v}, {w, x, y, z}};// 空字符根节点入队res.add();while(res.peek().length() ! digits.length()){String remove res.poll();//出队// 根据当前拼接字符或者说当前节点的值可以判断出我们需要拼接第几个字符// 比如最开始为空字符说明我们要为其拼接第一个字符// 它对应的字符为 digits.charAt(remove.length())// 由于字符是从 2-9但是我们的对应表数组下标从 0 开始// 即比如字符 2 对应的是 tab[0]// 所以这个字符对应的可能选项为// tab[digits.charAt(remove.length()) - 2]char[] chars tab[digits.charAt(remove.length()) - 2];// 拼接每种可能再入队for(int i0;ichars.length;i){res.add(removechars[i]);}}return res;}既然可以 bfs那么我们难免会想到用 dfs还是一样的原理这里的递归终止条件就是得到一种可能我们就记录并 return否则还是根据不同的可能性递归。其实按道理这个逻辑是回溯所以需要撤销操作比如我们得到了 ad 后应该复位成 a再得到 ae-a-af然后复位成空字符串继续得到 b-bd-b-be...否则你可能得到 ad 以后别的递归部分使用到的 str 就是从 ad 开始拼接得到比如 ade、adef但是由于递归时每个字符串都是新的对象不会污染每个可能性分支也就不用撤销操作了 LinkedListString res new LinkedList();char[][] tab {{a, b, c}, {d, e, f}, {g, h, i},{j, k, l}, {m, n, o}, {p, q, r, s},{t, u, v}, {w, x, y, z}};String digits;public ListString letterCombinations(String digits) {// 防空if (digits null || digits.isEmpty())return res;this.digits digits;dfs();return res;}public void dfs(String str){if(str.length() digits.length()){res.add(str);return;}char[] chars tab[digits.charAt(str.length()) - 2];for(int i0;ichars.length;i){dfs(strchars[i]);}}
