BFS solution using Queue


  • 0
    K
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits.length() == 0) return res;
        String[] lookUp = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        LinkedList<String> queue = new LinkedList<>();
        queue.offer("");
        int pos = 0;
        while (pos < digits.length()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String pre = queue.poll();
                String cur = lookUp[digits.charAt(pos) - '0'];
                for (int j = 0; j < cur.length(); j++) {
                    queue.offer(pre+cur.charAt(j));
                }
            }
            pos++;
        }
        res.addAll(queue);
        return res;
     }

Log in to reply
 

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