Concise 15 line Java Iterative Solution, very Straight Forward with Brief Explanation


  • 10
    M

    Assume we have current answer {x1,x2,x3,x4} in the list and there is one more digit to go. The last digit has two choices: "a" and "b"; Then what we do is to first assign "a" to each element in the current answer list and put we get into a new list, {x1a,x2a,x3a,x4a}. Then assign "b" and we get {x1a,x2a,x3a,x4a,x1b,x2b,x3b,x4b}. That's the basic operation for one digit.
    Starting from an empty list, do the previous steps digit by digit. And your answer will finally come out.

    public List<String> letterCombinations(String digits) {
    	String[] data = new String[] { " ", "", "abc", "def", "ghi", "jkl",
    			"mno", "pqrs", "tuv", "wxyz" };
    	List<String> ans = new ArrayList<String>();
    	for (int i = 0; i < digits.length(); i++) {
    		char[] c = data[digits.charAt(i) - '0'].toCharArray();
    		List<String> sub = new ArrayList<String>();
    		for (int j = 0; j < c.length; j++) {
    			if (ans.isEmpty())
    				ans.add("");
    			for (String s : ans) {
    				sub.add(s + c[j]);
    			}
    
    			ans = sub;
    		}
    	}
    	return ans;
    
    }

  • 1
    C

    Good sulotion. But I think there is mistake in the code.

    for (int j = 0; j < c.length; j++) {
    if (ans.isEmpty())
    ans.add("");
    for (String s : ans) {
    sub.add(s + c[j]);
    }
    ans = sub;
    }

    should be changed to :

    for (int j = 0; j < c.length; j++) {
    if (ans.isEmpty())
    ans.add("");
    for (String s : ans) {
    sub.add(s + c[j]);
    }
    }
    ans = sub;


  • 2
    L

    Your iterative idea is good, but I think you code has errors, the correct should be

    public List<String> letterCombinations(String digits) {
    		String[] data = new String[] { " ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
    		List<String> res = new ArrayList<String>();
    		for (int i = 0; i < digits.length(); i++) {
    			char[] letters = data[digits.charAt(i) - '0'].toCharArray();
    
    			List<String> sub = new ArrayList<String>();
    			if (res.isEmpty()) {
    				res.add("");
    			}
    			for (String s : res) {
    				for (int j = 0; j < letters.length; j++) {
    					sub.add(s + letters[j]);
    				}
    			}
    			res = sub;
    
    		}
    		return res;
    	}
    

Log in to reply
 

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