Simple 1ms Java solution using recursion


  • 0

    To this problem, recursion is a good solution. The code is self-explanatory。

    private static String[][] refer={{},{},{"a","c","b"},{"d","e","f"},
    		{"g","h","i"},{"j","k","l"},{"m","n","o"},{"p","q","r","s"},
    		{"t","u","v"},{"w","x","y","z"}};
    public static List<String> letterCombinations(String digits) {
    	List<String> result = new ArrayList<String>();
    	if (digits.length() == 0)
    		return result;
    	result = letterCombination(0, digits);
    	return result;
    }
    private static List<String> letterCombination(int start, String digits) {
    	List<String> result = new ArrayList<String>();
    	if (start == digits.length()) {
    		result.add("");
    		return result;
    	}
    	List<String> temp = letterCombination(start + 1, digits);
    	int index = digits.charAt(start) - '0';
    	for (String first: refer[index]) {
    		for (String second: temp) {
    			result.add(first + second);
    		}
    	}
    	return result;
    }

  • 0
    J

    Same idea here

        public List<String> letterCombinations(String digits) {        
            List<String> list = new ArrayList<>();
            if(digits.length() == 0)
                return list;
            String[] map = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
            backtrack(list,digits,map,0,"");
            return list;
        }
        private void backtrack(List<String> list, String digits, String[] map,int i, String str) {
            if(str.length() == digits.length())
                list.add(str);
            if(i<digits.length()) {
                int x = Character.getNumericValue(digits.charAt(i));
                for(char c : map[x].toCharArray()){
                    backtrack(list,digits, map, i+1,str+c);
                }
            }
        }

Log in to reply
 

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