O(4^n) recursive solution


  • 0
    M
    public class Solution {
        private static final String[] str = {"0", "1", "abc","def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        public List<String> letterCombinations(String digits) {
            List<String> list = new ArrayList<String>();
            if(digits.length()<1){
                return list;
            }
            char[] arr = new char[digits.length()];
            helper(digits, 0, list, arr);
            return list;
        }
        private void helper(String digits, int digit, List<String> list, char[] arr){
            if(digit == digits.length()){
                list.add(new String(arr));
                return;
            }
            for(int i=0; i<str[Integer.parseInt(digits.charAt(digit)+"")].length(); i++){
                    char ch = str[Integer.parseInt(digits.charAt(digit)+"")].charAt(i);
                    arr[digit] = ch;
                    helper(digits, digit+1, list, arr);
                }
            }
    }
    

Log in to reply
 

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