Leetcode #17 Letter Combinations of a Phone Number

Writer: Steven, Lee

Date: 12/21, Friday

Purpose: Solving #17 Letter Combinations of a Phone Number

Level: Medium

Percentage: 39.3% have solved this problem

Time: it took me 30 minutes :)

Dfs BackTracking programming  * reference * 

=> https://www.hackerearth.com/practice/basic-programming/recursion/recursion-and-backtracking/tutorial/

한국어 버전은 밑에 있습니다.

* Caution * Before you read the solution that I used, you need to solve this problem by yourself 

* Description *

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

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

* Example *

Example:

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

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

* What is the Idea? *

 There are some points that we need to consider. First, Check out all elements to make combinations. Second, There are no duplicated letters if given numbers are not the same. So what is the best way to solve the problem? I think backtracking is a good choice. Because we can find out all the possibilities. and also, we can avoid repetition accesses with the skill. 

 1. We need to convert numbers to letters based on the map.

2. Do backtracking with letters and find out combinations and store in an array

3. Return the array :)

* Check *
you can check out your answer on this site.

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

(한국어)

* 난이도는 중간입니다.

* 오직 39.3%만이 이 문제를 풀었습니다.

* 저는 30분 정도가 걸렸습니다. ^^/

Backtracking을 이용하는 것을 추천합니다 * 참고자료 *

=> https://www.hackerearth.com/practice/basic-programming/recursion/recursion-and-backtracking/tutorial/

* 주의 *  솔루션을 읽기 전에 스스로 문제를 푸실 수 있어야 합니다.

* 지문 *

 2 - 9까지의 숫자가 포한된 문자열이 주어집니다. 숫자가 표현할 수 있는 모든 문자조합들을 반환하세요.

숫자에서 문자로 변환된 룰은 맵이 아래쪽에 있습니다. 1은 어떤 문자도 표현하지 않습니다.

* Example *

Example:

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

Note:

위에 있는 답이 비록 사전식으로 되어 있을지라도 답은 당신이 원하는 순서로 제출할 수 있습니다.

* 아이디어 *

 먼저 우리들이 주의깊게 관찰해야 할 부분이 있습니다. 조합들을 만들기 위해 모든 요소들을 다 찾아봐야 합니다. 두 번째, 만약 주어진 숫자가 중복이 있지 않으면 문자들 또한 중복이 있으면 안됩니다. 그렇다면 무엇이 가장 좋은 방법일까요? 제 생각에는 backtracking이 괜찮은 선택이라고 생각합니다. 왜냐하면 이 기술로 모든 요소를 접근할 수 있고 또한 중복을 피할 수 있기 때문이죠.

  

 1. 주어진 숫자들을 모두 글자로 바꿉니다.

2. Backtracking 기법을 사용한 후 나오는 조합들을 array에 저장을 합니다.

3. 그 Array를 반환합니다. :)

* Check *

이 사이트에서 정답의 유무를 확인하실 수 있습니다.

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

Code & 코드

You need to read the code by yourself

스스로 코드를 읽을 줄 알아야 합니다.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class LetterCombinationsOfAPhoneNumber_17 {
    public static List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<String>();
        HashMap<Integer, String> map = new HashMap<Integer, String>();
        if(digits.isEmpty()) return result;
        
        String[] collections = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        
        for(int i = 0 ; i < digits.length() ; i++) {
        	map.put(i, collections[Integer.parseInt(digits.substring(i,i+1))]);
        }     
        letterCombinations(map, result, 0, digits.length(), "");
        return result;
    }
    public static void letterCombinations(HashMap<Integer, String> map, List<String> result, int start, int end, String combination) {
    	if(start == end) {
    		result.add(combination);
    		return;
    	}
    	String item = map.get(start);
    	for(int i = 0 ; i < item.length() ; i++) {
    		combination += item.charAt(i);
    		letterCombinations(map, result, start + 1, end, combination);
    		combination = combination.substring(0, combination.length() -1);
    	}
    }
	public static void main(String[] args) {
		String digits = "33";
		List<String> result = letterCombinations(digits);
		System.out.println(result);
	}
}