• API
• FAQ
• Tools
• Archive
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()) {
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.

Top