[LeetCode] 전화번호 문자 조합

(:40)

Letter Combinations of a Phone Number - LeetCode

문제 이해하기

2-9까지의 숫자로 이루어진 문자열이 주어질 때,

각 숫자에는 어떤 letter들이 매핑되어있음

• 2에는 a,b,c
• 3에는 d,e,f

조합을 만들라는 것은.. 예를들어 “23”이 주어지면

• 23
  • 2에는 a,b,c
  • 3에는 d,e,f
• 32 ( X) ← 이건 고려하지 않음.

문제 풀이

1. 각 숫자 문자에 매핑되는 문자열들을 매핑 ( Map ) → 각 숫자에 대한, 선택지인 char[]
2. StringBuilder를 사용하여, 각 조합을 생성하여 String으로 리턴
   • 조합 자체는 char[] 에다가 채워 넣도록 한다. ( 배열을 사용하면 덮어씌울 수가 있어서 )

---

조합 생성하기

• 가장 기본 : dfs 를 사용한 백트랙킹

class Solution {
    // 각 숫자(String) 에 매핑되는 letter들의 list
    public Map<Character, char[]> map = new HashMap<>();
    public String input;
    public StringBuilder sb = new StringBuilder("");
    public char[] comb;
    public ArrayList<String> answer = new ArrayList<>();
    public void initMap(){
        map.put('2',new char[]{'a','b','c'});
        map.put('3',new char[]{'d','e','f'});
        map.put('4',new char[]{'g','h','i'});
        map.put('5',new char[]{'j','k','l'});
        map.put('6',new char[]{'m','n','o'});
        map.put('7',new char[]{'p','q','r','s'});
        map.put('8',new char[]{'t','u','v'});
        map.put('9',new char[]{'w','x','y','z'});
    }

    public List<String> letterCombinations(String digits) {
        input = digits;
        if(digits.length() == 0)return answer
        initMap();
        comb = new char[digits.length()];
        dfs(0);
        return answer;

    }
		// // digits 에서 현재 선택해야하는 숫자의 index
    public void dfs(int idx){
        if(idx >= input.length()){
            answer.add(sb.append(comb).toString());//StringBuilder를 사용하여 char[]->String
            sb.delete(0,sb.length()); // 현재 생성된 이 조합을 sb에서는 제거
            return;
        }
				// // select : 해당 digit 에 대해 매핑되는 characters
        char[] select = map.get(input.charAt(idx));
        for (Character c : select) {
            comb[idx] = c; // digits.charAt(idx) 에 대응하는 letter하나를 선택
            dfs(idx+1); // digits의 다음 글자를 선택하러 넘어감
        }
    }
}

파이썬으론 어떻게 푸나??

파이썬에서 훨씬 간단해지는 이유는

str ="abc"
for j in str:
	print(j)

이거를 해보면

a

b

c

이렇게 출력됨

파이썬은..잘 못하니까.. 이해되는 상위 코드 복붙..

• 파이썬에서는 매번 문자열 생성하는게 별 상관이 없나?? 파이썬에서도문자열은 immutable한 것으로 알고 있는데 이런식으로 매 번 s+c를 해도 time complexity가 그리 높지 않은 듯;;

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        mapL = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        res = []
        if digits == "": return res
        def dfs(i,s):
            if i == len(digits):
                res.append(s)
                return
            for c in mapL[digits[i]]:
                dfs(i+1,s+c)
                
        dfs(0,"")
        return res