SHARE
TWEET

17. Letter Combinations|Time:O(3^N*4^M)|Space: O(3^N*4^M)

a guest Aug 19th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Problem: https://leetcode.com/problems/letter-combinations-of-a-phone-number
  2. // Solution: https://leetcode.com/problems/letter-combinations-of-a-phone-number/solution/
  3.  
  4. class Solution {
  5.     private static final Map<Character, String[]> mappings = new HashMap<>();
  6.     {
  7.         mappings.put('2', new String[] {"a", "b", "c"});
  8.         mappings.put('3', new String[] {"d", "e", "f"});
  9.         mappings.put('4', new String[] {"g", "h", "i"});
  10.         mappings.put('5', new String[] {"j", "k", "l"});
  11.         mappings.put('6', new String[] {"m", "n", "o"});
  12.         mappings.put('7', new String[] {"p", "q", "r", "s"});
  13.         mappings.put('8', new String[] {"t", "u", "v"});
  14.         mappings.put('9', new String[] {"w", "x", "y", "z"});
  15.     }
  16.     public List<String> letterCombinations(String digits) {
  17.         List<String> result = new ArrayList<>();
  18.         if(digits.length() == 0) return result;
  19.         backtrack(result, "", digits, 0);
  20.         return result;
  21.     }
  22.    
  23.     private void backtrack(List<String> result, String current, String digits, int idx) {
  24.         if(current.length() == digits.length()) {
  25.             result.add(current);
  26.         }
  27.         for(int i = idx; i < digits.length(); i++) {
  28.             for(String j : mappings.get(digits.charAt(i))) {
  29.                 current += j;
  30.                 backtrack(result, current, digits, i+1);
  31.                 current = current.substring(0, current.length() - 1);
  32.             }
  33.         }
  34.     }
  35. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top