leetcode17 Letter Combinations of a Phone Number

snowell 發(fā)布于2019-08-14 18:09 / 3022人閱讀

摘要：題目要求也就是說(shuō)，將數(shù)字對(duì)應(yīng)的字母的排列組合的的所有可能結(jié)果都枚舉出來(lái)，順序不唯一。這種類型的題目一般需要求出上一種情況的前提下才可以得知下一種情況。這一種數(shù)據(jù)結(jié)構(gòu)通過(guò)來(lái)實(shí)現(xiàn)。相比于上一種思路中，內(nèi)存占用更小，而且更加靈活。

題目要求

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.

也就是說(shuō)，將數(shù)字對(duì)應(yīng)的字母的排列組合的的所有可能結(jié)果都枚舉出來(lái)，順序不唯一。

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

思路一：遞歸

當(dāng)我們無(wú)法直接得出結(jié)果的時(shí)候，我們可以借助遞歸讓計(jì)算機(jī)幫我們考慮每一種情況并逐級(jí)得出當(dāng)前的結(jié)果。在本思路中，我用了String數(shù)組來(lái)表示每一個(gè)按鍵對(duì)應(yīng)的字母，其中數(shù)組的下標(biāo)代表按鍵值。

    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
思路二：隊(duì)列（通過(guò)linkedlist實(shí)現(xiàn)）
從隊(duì)列頭獲得上一種情況的結(jié)果，經(jīng)過(guò)處理后添加到隊(duì)列尾。這一種數(shù)據(jù)結(jié)構(gòu)通過(guò)linkedList來(lái)實(shí)現(xiàn)。相比于上一種思路中ArrayList，linkedList內(nèi)存占用更小，而且更加靈活。
    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

想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~