题解 | #牛名生成器# Java
牛名生成器
https://www.nowcoder.com/practice/f82fe408de8f4fbdbc30162d6b3e65bb
首先,我们定义一个 letterCombinations
函数,它接受一个字符串 digits
作为参数。我们首先创建一个哈希表 dict
来存储数字到字母的映射,然后创建一个空的结果列表 ans
。
接下来,我们调用 dfs
函数,它接受结果列表 ans
、临时字符串 tmp
、字符串 digits
、哈希表 dict
和起始索引 idx
作为参数。在 dfs
函数中,我们首先检查起始索引是否等于字符串长度,如果是,则将临时字符串加入结果列表中并返回。
然后,我们获取字符串中当前索引位置的字符,并在哈希表中查找对应的字母字符串。接着,我们遍历这个字母字符串,对于每个字母,将其加入临时字符串中,并递归调用 dfs
函数,将起始索引加1。最后,我们将临时字符串中最后一个字符删除。
当所有可能的组合都被找到后,我们将结果列表转换为字符串数组并返回。
import java.util.*; public class Solution { public String[] letterCombinations (String digits) { HashMap<Character, String> dict = new HashMap<>(); List<String> ans = new ArrayList<>(); dict.put('2', "abc"); dict.put('3', "def"); dict.put('4', "ghi"); dict.put('5', "jkl"); dict.put('6', "mno"); dict.put('7', "pqrs"); dict.put('8', "tuv"); dict.put('9', "wxyz"); dfs(ans, new StringBuilder(), digits, dict, 0); return ans.toArray(new String[0]); } void dfs(List<String> ans, StringBuilder tmp, String digits, HashMap<Character, String> dict, int idx) { if (idx == digits.length()) { ans.add(tmp.toString()); return; } char c = digits.charAt(idx); String str = dict.get(c); for (int i = 0; i < str.length(); i++) { tmp.append(str.substring(i, i + 1)); dfs(ans, new StringBuilder(tmp), digits, dict, idx + 1); tmp.deleteCharAt(tmp.length() - 1); } } }
我真tm的棒!
算法题刷刷刷 文章被收录于专栏
数组、链表、栈、队列、堆、树、图等。 查找和排序:二分查找、线性查找、快速排序、归并排序、堆排序等。 动态规划:背包问题、最长公共子序列、最短路径 贪心算法:活动选择、霍夫曼编码 图:深度优先搜索、广度优先搜索、拓扑排序、最短路径算法(如 Dijkstra、Floyd-Warshall) 字符串操作:KMP 算法、正则表达式匹配 回溯算法:八皇后问题、0-1 背包问题 分治算法:归并排序、快速排序