17. Letter Combinations of a Phone Number

문제

 

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

 

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

 

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

 

 

 

https://leetcode.com/problems/letter-combinations-of-a-phone-number

 

 

풀이

숫자별로 지정된 문자들에 대해 모든 조합을 작성하는 문제였다.

각 숫자별로 나올 수 있는 문자들을 2차원 배열에 저장해 놓고, 각 숫자에 지정된 문자들을 추가하면서 다음 숫자를 확인하여 이어가도록 코드를 작성했다.

현재까지 만든 문자열과 확인한 숫자의 길이가 같기 때문에, 이를 이용하여 dfs를 마무리하도록 했다.

 

다행이었던 점은 문자만 존재한 2~9까지의 숫자만 입력값으로 준다는 점과 문자열 길이가 최대 4자리라서 소요 시간 걱정은 덜 수 있었다.

 

코드

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<String>();
		
		if(digits.length() == 0) {
			return res;
		}
		
        String[][] mapping = {{}, {}, 
        		{"a","b","c"}, 
        		{"d","e","f"}, 
        		{"g","h","i"}, 
        		{"j","k","l"}, 
        		{"m","n","o"}, 
        		{"p","q","r","s"}, 
        		{"t","u","v"}, 
        		{"w","x","y","z"}
        		};
        
        dfs(digits, "", mapping, res);
        
        
        return res;
    }

    public void dfs(String digits, String temp_str, String[][] mapping, List<String> res) {
		if(temp_str.length() == digits.length()) {
			res.add(temp_str);
			return;
		}
		
		int idx = Character.getNumericValue(digits.charAt(temp_str.length()));
		for(int i = 0; i < mapping[idx].length; i++ ) {
			dfs(digits, temp_str + mapping[idx][i], mapping, res);
		}
	}
}

 

 

결과

Runtime : 1 ms

Memory Usage : 41.90 MB