Accepted Java solution based on Backtracking.


  • 1
    O
    public class Solution {
        public List<String> letterCombinations(String digits) {
        	if (digits.contains("0") || digits.contains("1") || digits.length() == 0) {
        		return new ArrayList<String>();
        	}
        	List<String> res = new ArrayList<String>();
        	String[] phone = new String[10];
        	phone[2] = "abc";
        	phone[3] = "def";
        	phone[4] = "ghi";
        	phone[5] = "jkl";
        	phone[6] = "mno";
        	phone[7] = "pqrs";
        	phone[8] = "tuv";
        	phone[9] = "wxyz";
        	String str = new String();
    		letterCombinationHelper(digits, 0, str, phone, res);
            return res;
        }
        
        public static void letterCombinationHelper(String digits, int start, String str, String[] phone, List<String> res) {
        	if(digits.length() == start) {
        		res.add(str);
        	} else {
    			int idx = digits.charAt(start) - 48;
    			for(int j = 0; j < phone[idx].length(); j++) {
    				str += phone[idx].charAt(j); 
    				letterCombinationHelper(digits, start+1, str, phone, res);
    				str = str.substring(0, str.length()-1);
    			}
        	}
        }
    }
    

Log in to reply
 

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