Dynamic for문 - 백트랙킹 기법 (back tracking)

                                    🤔 각 digit에 해당하는 dic을 만들어서 배열 형태로 저장해서 조합을 만들면 될 것 같다.

🤔 근데 포인터 관리를 어떻게 해야하지??

✅ 자료구조 : dictionary {"2": "abc", ... ,}

✅ [[a, b, c]. [d, e, f]] or ["abc", "def"]
>>> ad, ae, af, bd, be, bf, cd, ce, cf를 만들어야한다.
>>> for문 사용하면 되잖아>

✅ for [a, b, c].. in [[a, b, c], [d, e, f], ...,] or ["abc", "def", ..,]:
       for char1 in [a,b,c]:
            for char2 in [d,e,f]:
                 for char3 in [...]:
                     char1 + char2 + char 3...

>>> 4중첩 for문인데 크기가 작아서 상관은 없을 것 같음
>>> 구현이 문제다

                                    🤔 동적으로 for문을 돌려야하는데 이게 구현이 너무 까다롭다. 좀더 쉬운 방법이 없을까?

🤔 ["abc", "def"]형태를 "abcdef"로 두고 포인터를 체크하면 어떨까?
>>> 그럼 포인터도 digit만큼 동적으로 갯수가 변한다 -> 이 역시 구현이 힘들다.

🤔 idx가 digit = 1 -> 0~2, 2 -> 0~5, 3-> 0~8, 4 -> 0~8인 점을 이용할 수 없을까?

💀 오래 고민해봤는데 결국에는 동적으로 포인터를 생성 해야 한다.
-> 이걸 어떻게 할 수 있을까??

                                    ✅ n = len(digit)

✅ if n == 1 : -> easy
   if n >= 2 : -> difficult for impl

✅ 그냥 if문으로 나눠서 풀어보자 ...

                                    class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        alp = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", '9': "wxyz"}
        results = []
        strs = []

        n = len(digits)
        if n == 1:
            strings = alp[digits[0]]

            for s in strings:
                results.append(s)

        if n == 2:
            for d in digits:
                strs.append(alp[d])

            for str1 in strs[0]:
                for str2 in strs[1]:
                    results.append(str1 + str2)

        if n == 3:
            for d in digits:
                strs.append(alp[d])

            for str1 in strs[0]:
                for str2 in strs[1]:
                    for str3 in strs[2]:
                        results.append(str1 + str2 + str3)
        if n == 4:
            for d in digits:
                strs.append(alp[d])

            for str1 in strs[0]:
                for str2 in strs[1]:
                    for str3 in strs[2]:
                        for str4 in strs[3]:
                            results.append(str1 + str2 + str3 + str4)
        return results

                                    ✅ 이전 배열과 현재 배열을 합친다.

✅ 합친 배열을 다음 깊이에 전달한다.

✅ 끝에 도달했다면, 합쳐진 배열을 하나씩 return한다.

                                    class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []

        alp = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", '9': "wxyz"}
        n = len(digits)

        strs = []

        for d in digits:
            strs.append(alp[d])

        if n == 1:
            result = []
            for s in strs[0]:
                result.append(s)
            return result

        def backtracking(before, path):
            if path == n:
                return before

            curr = alp[digits[path]]

            new_str = []
            for b in before:
                print("b", b)
                for c in curr:
                    new_str.append(b + c)
                    print("c", c)

            path += 1
            maded = backtracking(new_str, path)
            return maded

        result = backtracking(alp[digits[0]], 1)

        return result

                                    ✅ 모든 각 문자열에 대해 깊이를 생성한다.

🗝️ 내가 작성한 코드는 ["a", "b", "c"]를 넣어서 ["ad", "ae", "af", "bd", ...] 를 만들고
다시 넘겨서 ["adg", ...] 형태를 만든 후 마지막에 return한다.

👉 반면, 아래 코드는 ["a", "b", "c"]가 주어지면 "a", "b", "c"각각 따로 탐색이 이루어진다.

>>> dfs(idx, string)
>>> dfs(1, "a") dfs(1, "b") ,dfs(1, "c") 이런식으로 말이다.

👉 결론적으로 len(string) == len(digits)가 되는 순간 해당 String은 res에 넣어준다.
>>> 각각 개별적으로 문자열을 만든 후 res에 넣어주는 방식

                                    class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []

        alp = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", '9': "wxyz"}
        n = len(digits)
        result = []

        def backtracking(i, strs):
            if len(strs) == n:
                result.append(strs)
                return

            for c in alp[digits[i]]:
                backtracking(i + 1, strs + c)

        if digits:
            backtracking(0, "")

        return result