leetcode 17-Letter Combinations of a Phone Number(medium)

发布时间：2020-12-14 03:45:01 所属栏目：大数据来源：网络整理

导读：Given a string containing digits from? 2-9 ?inclusive,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. Note that 1 does not map to a

Given a string containing digits from?2-9?inclusive,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. Note that 1 does not map to any letters.

use hashmap to store digit and characters accordingly.

at ith position of input:

　　use queue to store the combinations of the first i digits,when adding new digits,just need to get every combination in the queue and add the new digit on each one.

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> list=new ArrayList<>();
        if(digits.length()==0) return list;
        Map<Character,String> map=new HashMap<>();
        map.put(‘2‘,"abc");
        map.put(‘3‘,"def");
        map.put(‘4‘,"ghi");
        map.put(‘5‘,"jkl");
        map.put(‘6‘,"mno");
        map.put(‘7‘,"pqrs");
        map.put(‘8‘,"tuv");
        map.put(‘9‘,"wxyz");
        Queue<String> queue=new LinkedList<>();
        queue.offer("");
        for(char c:digits.toCharArray()){
            int num=queue.size();
            for(int i=0;i<num;i++){
                String str=queue.poll();
                for(char x:map.get(c).toCharArray()){
                    queue.offer(str+x);
                }
            }
        }
        while(!queue.isEmpty()){
            list.add(queue.poll());
        }
        return list;
    }
}

不要老是想着hashmap！

如果index可以用数组下标表示就避免用hashmap，数组的维护比hashmap要容易快捷的多

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> list=new ArrayList<>();
        if(digits.length()==0) return list;
        String[] record=new String[]{null,null,"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        Queue<String> queue=new LinkedList<>();
        queue.offer("");
        for(char c:digits.toCharArray()){
            int num=queue.size();
            for(int i=0;i<num;i++){
                String str=queue.poll();
                for(char x:record[c-‘0‘].toCharArray()){
                    queue.offer(str+x);
                }
            }
        }
        while(!queue.isEmpty()){
            list.add(queue.poll());
        }
        return list;
    }
}

backtracking:

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> list=new ArrayList<>();
        if(digits.length()==0) return list;
        String[] record=new String[]{null,"wxyz"};
        getCombination(digits,record,"",0,list);
        return list;
    }
    public void getCombination(String digits,String[] record,String str,int index,List<String> list){
        if(index>=digits.length()){
            list.add(str);
            return;
        }
        for(int i=0;i<record[digits.charAt(index)-‘0‘].length();i++){
            getCombination(digits,str+record[digits.charAt(index)-‘0‘].charAt(i),index+1,list);
        }
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!