摘要:最新更新請見深度優先搜索復雜度時間空間遞歸棧空間思路首先建一個表,來映射號碼和字母的關系。然后對號碼進行深度優先搜索,對于每一位,從表中找出數字對應的字母,這些字母就是本輪搜索的幾種可能。
Letter Combinations of a Phone Number 最新更新請見:https://yanjia.me/zh/2019/01/...
Given a digit string, 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.
Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Note: Although the above answer is in lexicographical order, your answer could be in any order you want.
時間 O(N) 空間 O(N) 遞歸棧空間
思路首先建一個表,來映射號碼和字母的關系。然后對號碼進行深度優先搜索,對于每一位,從表中找出數字對應的字母,這些字母就是本輪搜索的幾種可能。
注意用StringBuilder構建臨時字符串
當臨時字符串為空時,不用將其加入結果列表中
代碼public class Solution { Listres; public List letterCombinations(String digits) { // 建立映射表 String[] table = {" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; StringBuilder tmp = new StringBuilder(); res = new LinkedList (); helper(table, 0, tmp, digits); return res; } private void helper(String[] table, int idx, StringBuilder tmp, String digits){ if(idx == digits.length()){ // 找到一種結果,加入列表中 if(tmp.length()!=0) res.add(tmp.toString()); } else { // 找出當前位數字對應可能的字母 String candidates = table[digits.charAt(idx) - "0"]; // 對每個可能字母進行搜索 for(int i = 0; i < candidates.length(); i++){ tmp.append(candidates.charAt(i)); helper(table, idx+1, tmp, digits); tmp.deleteCharAt(tmp.length()-1); } } } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/64560.html
摘要:題目要求也就是說,將數字對應的字母的排列組合的的所有可能結果都枚舉出來,順序不唯一。這種類型的題目一般需要求出上一種情況的前提下才可以得知下一種情況。這一種數據結構通過來實現。相比于上一種思路中,內存占用更小,而且更加靈活。 題目要求 Given a digit string, return all possible letter combinations that the numbe...
摘要:而按鍵和字母的對應關系如上圖。這將成為下一次操作的前序字符串。對于每一個不同的前序字符串,我們都要在其后面分別加上當前鍵所表示的不同字符,再將獲得的結果字符串加入里面。 題目詳情 Given a digit string, return all possible letter combinations that the number could represent. mapping o...
摘要:前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫~現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。 順序整理 1~50 1...
摘要:不過好消息是,在事件發生的二十四小時以后,我發現我的賬號解禁了,哈哈哈哈。 本文最初發布于我的個人博客:咀嚼之味 從昨天凌晨四點起,我的 Leetcode 賬號就無法提交任何代碼了,于是我意識到我的賬號大概是被封了…… 起因 我和我的同學 @xidui 正在維護一個項目 xidui/algorithm-training。其實就是收錄一些算法題的解答,目前主要對象就是 Leetcode。...
閱讀 3380·2021-11-22 09:34
閱讀 650·2021-11-19 11:29
閱讀 1350·2019-08-30 15:43
閱讀 2232·2019-08-30 14:24
閱讀 1867·2019-08-29 17:31
閱讀 1223·2019-08-29 17:17
閱讀 2617·2019-08-29 15:38
閱讀 2729·2019-08-26 12:10