My BFS AC solution. Any advising?


  • 0
    L
    public class Solution {
    
    private HashMap<String, List<String>> map = new HashMap<>();
    
    public void generateMapping() {
        map.put("2", new LinkedList<String>(Arrays.asList("a", "b", "c")));
        map.put("3", new LinkedList<String>(Arrays.asList("d", "e", "f")));
        map.put("4", new LinkedList<String>(Arrays.asList("g", "h", "i")));
        map.put("5", new LinkedList<String>(Arrays.asList("j", "k", "l")));
        map.put("6", new LinkedList<String>(Arrays.asList("m", "n", "o")));
        map.put("7", new LinkedList<String>(Arrays.asList("p", "q", "r", "s")));
        map.put("8", new LinkedList<String>(Arrays.asList("t", "u", "v")));
        map.put("9", new LinkedList<String>(Arrays.asList("w", "x", "y", "z")));
    }
    
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0 || digits == "1" || digits == "0") {
            return new LinkedList<String>(Arrays.asList(""));
        }
        generateMapping();
        
        String firstLetter = digits.substring(0, 1);
        LinkedList<String> queue = new LinkedList<String>();
        queue.addAll(map.get(firstLetter));
        
        for (int i = 1; i < digits.length(); ++i) {
            String nextDigit = digits.substring(i, i + 1);
            while(!queue.isEmpty()) {
                String s = queue.peek();
                if (s.length() != i) {
                    break;
                }
                queue.poll();
                List<String> letterList = map.get(nextDigit);
                for(String letter : letterList) {
                    queue.add(s + letter);
                }
            }
        }
        
        return queue;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.