(Python3) - LeetCode (Hard) : 1639. Number of Ways to Form a Target String Given a Dictionary

https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary

top down dp로 해결한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

MOD, 한 단어의 길이 word_len, target의 길이 target_len, 각 단어의 열별 알파뱃의 빈도수를 저장할 해시맵인 freq_map, j번째 타겟의 문자를 만들기 위해 k번째 열의 word를 선택할 경우 만들 수 있는 문자들의 경우의 수를 의미하는 total_ways를 선언 후 적절히 초기화합니다.

📔 풀이과정

words의 길이가 모두 같기 때문에 단어들을 선택할 때 열별로 선택여부를 결정할 수 있습니다. words = ["abba", "baab", "abcd"]가 있을 때 각 문자열들을 세로로 배치하면 열을 선택한다는 의미를 파악해볼 수 있습니다.

words = [

  "abba",

  "baab",

  "abcd"

]

 

여기서 0번째 열을 선택한다면

words = [

  "abba",

  "baab",

  "abcd"

]

 

1번째 열을 선택한다면

words = [

  "abba",

  "baab",

  "abcd"

]

로 선택하게 됩니다.

 

freq_map에서 {0번째 열을 선택했을때 알파뱃 : 알파뱃별 빈도수} 형태로 저장되므로 다음과 같습니다.

{

  0: {'a':2, 'b':1}

  1: {'a':1, 'b':2}

}

 

여기서 target의 j번째 문자를 만들기 위해 다음 두가지 방식을 freq_map에서 적용해 모든 상태를 검사할 수 있습니다. 재귀형태로 호출하게 되면 다음 상태가 될 수 있는 모든 후보들을 쉽게 검사할 수 있습니다.

1. words의 k번째 열을 선택하지 않을 경우: 선택하지 않는 채로 k+1번째 열에 대해 다음 재귀함수 호출

2. words의 k번째 열을 선택해 freq_map[k]중 target[j]가 있다면 해당 문자의 빈도수 * 다음 재귀함수 호출

 

1,2번 방식은 같은 인자로 호출되는 경우가 많아지므로 memoization을 사용해줍니다. 이는 total_ways를 사용해 이미 계산된 total_ways[j][k]가 있다면 해당 값을 바로 반환하는 방식으로 호출을 막습니다.

k번째 열을 선택해 j개의 문자들을 만드는 계산이 한 번씩 이루어지므로 시간 복잡도는 O(J * K)가 됩니다.

 

이제 해당 아이디어로 재귀함수 dp를 만들어 봅시다. 인자로 j번째 target의 index와 k번째 열 2개를 넘겨줍니다. 

기저 case는 다음과 같습니다.

1. j번째 문자까지 만들어서 target_len만큼 호출이 되었다면 원하는 target문자가 만들어졌으므로 1을 반환합니다.

2. j번째 열을 words에서 선택하거나 선택하지 않음으로써 k번째까지 도달했다면 더 이상 선택할 수 없으며 target 문자를 만들지 못했으므로 0을 반환합니다.

 

탐색은 다음처럼 진행합니다.

1. ways를 선언해 먼저 k번째 열을 선택하지 않고 j, k+1에 대해 선택하므로 dp(j, k+1)을 호출한 값을 저장합니다.

2. k번째 열을 선택해 해당 freq_map[k][target[j] 빈도수 * dp(j+1,k+1) 을 호출합니다. MOD연산을 적용해 total_ways에 값을 갱신합니다.

 

 

📔 정답 출력 | 반환

dp(0,0)을 반환합니다. 모든 재귀함수가 호출되고 끝에서부터 반환되는 값이 total_ways[0][0]에 저장되게 됩니다. 해당 값이 최종적으로 반환됩니다.

---

📕 Code

📔 Python3

from collections import defaultdict
class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        MOD = 10**9 + 7
        word_len = len(words[0])
        target_len = len(target)
        freq_map = [defaultdict(int) for _ in range(word_len)]
        for word in words:
            for j, char in enumerate(word):
                freq_map[j][char] += 1
        total_ways = [[-1]*word_len for _ in range(target_len)]
        def dp(j, k):
            if j == target_len:
                return 1
            if k == word_len:
                return 0
            if total_ways[j][k] != -1:
                return total_ways[j][k]
            ways = dp(j,k+1)
            ways += freq_map[k][target[j]] * dp(j+1,k+1) % MOD
            total_ways[j][k] = ways % MOD
            return total_ways[j][k]
        return dp(0, 0)

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.