Java - Bottom Up recursion. simple.


  • 0
    D

    Prepend possible mappings of the first character to all results of letterCombinations(digits.substring(1)). There was a weird base case I had to step around when the input is an empty string, which is expecting an empty array. The traditional base case would be to return an array with an empty string.

    public class Solution {
        
        String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        
        public List<String> letterCombinations(String digits) {
            
            List<String> result = new ArrayList<>();
            
            if (digits.length() == 0) {
                // weird base case wants an empty list, when we get empty input.
                return result;
            } 
        
            // strip the first character        
            int num = Character.getNumericValue(digits.charAt(0));
            String charSet = mapping[num];
    
            List<String> subResult = letterCombinations(digits.substring(1));
            // we do this weird case because the weird base case.
            if (subResult.isEmpty()) {
                subResult.add("");
            }
            
            // prepend all possible letter mappings to every subsequence we've seen.
            for (String sub : subResult) {
                for (char c : charSet.toCharArray()) {
        			result.add(c + sub);
        		}
            }
            
            return result;
        }
    }
    

Log in to reply
 

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