leetcode17 Letter Combinations of a Phone Number

snowell 發布于2019-08-14 18:09 / 3017人閱讀

摘要：題目要求也就是說，將數字對應的字母的排列組合的的所有可能結果都枚舉出來，順序不唯一。這種類型的題目一般需要求出上一種情況的前提下才可以得知下一種情況。這一種數據結構通過來實現。相比于上一種思路中，內存占用更小，而且更加靈活。

題目要求

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.

也就是說，將數字對應的字母的排列組合的的所有可能結果都枚舉出來，順序不唯一。

leetcode給這道題目加了一個標簽很有意思，叫做Backtracking。點進去之后又很多類似的題目。這種類型的題目一般需要求出上一種情況的前提下才可以得知下一種情況。比如我必須先得知按下“2”后所有字母的可能值，才能在計算出“22”對應的可能值

思路一：遞歸

當我們無法直接得出結果的時候，我們可以借助遞歸讓計算機幫我們考慮每一種情況并逐級得出當前的結果。在本思路中，我用了String數組來表示每一個按鍵對應的字母，其中數組的下標代表按鍵值。

    String[] letters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List letterCombinations(String digits) {
        List result = new ArrayList();
        for(int i = 0 ; i letterCombinations(char digit, List currentList){
        int number = digit - "0";
        String letter = letters[number];
        if(letter.length()==0){
            return currentList;
        }
        
        if(currentList.size() == 0){
            for(int i = 0 ; i result = new ArrayList();
        for(int i = 0 ; i
思路二：隊列（通過linkedlist實現）
從隊列頭獲得上一種情況的結果，經過處理后添加到隊列尾。這一種數據結構通過linkedList來實現。相比于上一種思路中ArrayList，linkedList內存占用更小，而且更加靈活。
    String[] letters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List letterCombinations2(String digits) {
        LinkedList l = new LinkedList();
        if(digits.length()==0){
            return l;
        }
        l.add("");
        
        int empty = 0;
        for(int i = 0 ; i < digits.length() ; i++){
            int number = digits.charAt(i) - "0";

            String letter = letters[number];
            if(letter.length() == 0){
                empty++;
                continue;
            }
            while(l.peek().length() + empty == i){
                String peek = l.removeFirst();
                for(int j = 0 ; j

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 Combinations Letter automation of com first-letter

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/67027.html

leetcode 17 Letter Combinations of a Phone Number

摘要：而按鍵和字母的對應關系如上圖。這將成為下一次操作的前序字符串。對于每一個不同的前序字符串，我們都要在其后面分別加上當前鍵所表示的不同字符，再將獲得的結果字符串加入里面。題目詳情 Given a digit string, return all possible letter combinations that the number could represent. mapping o...

sean 2019-08-15 14:39 評論0 收藏0
[Leetcode] Letter Combinations of a Phone Number 電

摘要：最新更新請見深度優先搜索復雜度時間空間遞歸棧空間思路首先建一個表，來映射號碼和字母的關系。然后對號碼進行深度優先搜索，對于每一位，從表中找出數字對應的字母，這些字母就是本輪搜索的幾種可能。 Letter Combinations of a Phone Number 最新更新請見：https://yanjia.me/zh/2019/01/... Given a digit string...

fxp 2019-08-14 12:34 評論0 收藏0
leetcode 部分解答索引（持續更新～）

摘要：前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫～現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0
記一次作死 —— 被 Leetcode 封禁

摘要：不過好消息是，在事件發生的二十四小時以后，我發現我的賬號解禁了，哈哈哈哈。本文最初發布于我的個人博客：咀嚼之味從昨天凌晨四點起，我的 Leetcode 賬號就無法提交任何代碼了，于是我意識到我的賬號大概是被封了…… 起因我和我的同學 @xidui 正在維護一個項目 xidui/algorithm-training。其實就是收錄一些算法題的解答，目前主要對象就是 Leetcode。...

dackel 2019-08-19 17:06 評論0 收藏0
九宮格鍵盤輸入

摘要：九宮格鍵盤輸入給定一個數字字符串，返回數字可能代表的所有可能的字母組合。數字到字母的映射就像九宮格電話按鈕一樣如下圖。思路以為例，代表，只需要將其轉換成，然后處理，為，將這三個字符分別加到的每一個元素中，得到。重復此過程即可。九宮格鍵盤輸入 Letter Combinations of a Phone Number 給定一個數字字符串，返回數字可能代表的所有可能的字母組合。數字到...

Xufc 2019-07-25 12:04 評論0 收藏0