Explanatory and simple Java solution using recursion


  • 0
    L

    I think it is easy to strike that it should do a dfs-based search to figure out all permutations. Generally the idea behind these kind of problems is to try all combination for a particular number and then go to the next level and do the same at that level. The exit condition should be carefully chosen to stop the work when needed. Remember, a for loop is not required across the length of the string, since we don't care about combinations, we need pemutations only so we will go in depth for each character. Here is the code:

    public class Solution {
        final static Map<Character,List<Character>> map = new HashMap<>();
        static {
            map.put('1',Arrays.asList('1'));
            map.put('2',Arrays.asList('a','b','c'));
            map.put('3',Arrays.asList('d','e','f'));
            map.put('4',Arrays.asList('g','h','i'));
            map.put('5',Arrays.asList('j','k','l'));
            map.put('6',Arrays.asList('m','n','o'));
            map.put('7',Arrays.asList('p','q','r','s'));
            map.put('8',Arrays.asList('t','u','v'));
            map.put('9',Arrays.asList('w','x','y','z'));
        }
        public List<String> letterCombinations(String digits) {
            if(digits==null || digits.length()==0) {
                return Collections.emptyList();
            }
            List<String> list = new ArrayList<>();
            helper(list,digits,0,"");
            return list;
        }
        private void helper(List<String> list, String digits,int pos,String str) {
          if(digits.length()==pos){   
              list.add(str);
              return;
          }
          for(char c : map.get(digits.charAt(pos))) {
              helper(list,digits,pos+1,str+c);
          }
        }
    

Log in to reply
 

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