문제 링크

내 코드

Solution 참고.

Solution

Approach 1: Top-down Dynamic Programming

• 47ms, 58.31MB
• Complexity
  • Let $totalWords$ be the total number of words in the words matrix, and $wordLength$ and $targetLength$ represent the length of any word in words and the target string, respectively.
  • Time Complexity: $O(\text{wordLength} \cdot \text{targetLength} + \text{wordLength} \cdot \text{totalWords})$
  • Space Complexity: $O(\text{wordLength} \cdot \text{targetLength})$

class Solution {
public:
    int numWays(vector<string>& words, string target) {
        vector<vector<int>> dp(words[0].size(), vector<int>(target.size(), -1));
        vector<vector<int>> charFrequency(words[0].size(), vector<int>(26, 0));

        // Store the frequency of every character at every index.
        for (int i = 0; i < words.size(); i++) {
            for (int j = 0; j < words[0].size(); j++) {
                int character = words[i][j] - 'a';
                charFrequency[j][character]++;
            }
        }
        return getWords(words, target, 0, 0, dp, charFrequency);
    }

private:
    long getWords(vector<string>& words, string& target, int wordsIndex,
                  int targetIndex, vector<vector<int>>& dp,
                  vector<vector<int>>& charFrequency) {
        if (targetIndex == target.size()) return 1;
        if (wordsIndex == words[0].size() ||
            words[0].size() - wordsIndex < target.size() - targetIndex)
            return 0;

        if (dp[wordsIndex][targetIndex] != -1)
            return dp[wordsIndex][targetIndex];

        long countWays = 0;
        int curPos = target[targetIndex] - 'a';
        // Don't match any character of target with any word.
        countWays += getWords(words, target, wordsIndex + 1, targetIndex, dp,
                              charFrequency);
        // Multiply the number of choices with getWords and add it to count.
        countWays += charFrequency[wordsIndex][curPos] *
                     getWords(words, target, wordsIndex + 1, targetIndex + 1,
                              dp, charFrequency);

        return dp[wordsIndex][targetIndex] = countWays % 1000000007;
    }
};

GPT

이 코드는 문자열 배열 words에서 문자를 조합하여 주어진 target 문자열을 만드는 방법의 수를 계산합니다. 이 문제는 동적 프로그래밍(DP)을 사용해 해결하며, 효율적으로 문자열 조합을 탐색합니다.

---

문제 이해

문제 정의

• 주어진 문자열 배열 words에서 각 단어의 동일한 위치에 있는 문자를 조합해 target 문자열을 생성.
• 동일한 위치에서 선택할 수 있는 문자는 제한 없음.
• 가능한 조합의 수를 $10^9 + 7$로 나눈 나머지를 반환.

---

코드 분석

1. 주요 아이디어

1. 문자 빈도 저장:
   • charFrequency[j][c]: words에서 인덱스 $j$에 위치한 문자 $c$의 빈도를 저장.
2. 동적 프로그래밍:
   • dp[wordsIndex][targetIndex]: words의 위치 $wordsIndex$에서 시작해 target의 위치 $targetIndex$를 완성하는 방법의 수를 저장.
3. 두 가지 선택:
   • 현재 위치에서 문자를 선택하지 않음.
   • 현재 위치에서 문자를 선택하여 target의 다음 문자로 진행.

---

2. numWays 함수

a. 데이터 구조 초기화

vector<vector<int>> dp(words[0].size(), vector<int>(target.size(), -1));
vector<vector<int>> charFrequency(words[0].size(), vector<int>(26, 0));

• dp: 메모이제이션 배열로, 계산한 결과를 저장해 중복 계산 방지.
• charFrequency: words에서 각 위치의 문자 빈도를 저장.

b. 문자 빈도 계산

for (int i = 0; i < words.size(); i++) {
    for (int j = 0; j < words[0].size(); j++) {
        int character = words[i][j] - 'a';
        charFrequency[j][character]++;
    }
}

• $O(\text{words.size()} \times \text{words[0].size()})$의 시간 복잡도로 각 위치에서 문자의 빈도를 계산.

c. 동적 프로그래밍 함수 호출

return getWords(words, target, 0, 0, dp, charFrequency);

• 초기 위치 $(wordsIndex = 0, targetIndex = 0)$에서 시작.

---

3. getWords 함수

a. 기저 조건

if (targetIndex == target.size()) return 1;
if (wordsIndex == words[0].size() ||
    words[0].size() - wordsIndex < target.size() - targetIndex)
    return 0;

1. targetIndex == target.size():
   • target 문자열을 완성한 경우 방법의 수는 1.
2. wordsIndex == words[0].size():
   • words의 모든 위치를 탐색한 경우 방법의 수는 0.
3. words[0].size() - wordsIndex < target.size() - targetIndex:
   • 남은 문자가 충분하지 않은 경우 방법의 수는 0.

---

b. 메모이제이션 확인

if (dp[wordsIndex][targetIndex] != -1)
    return dp[wordsIndex][targetIndex];

• 이미 계산된 값이 있으면 반환해 중복 계산을 방지.

---

c. 동적 프로그래밍 점화식

long countWays = 0;
int curPos = target[targetIndex] - 'a';

// Don't match any character of target with any word.
countWays += getWords(words, target, wordsIndex + 1, targetIndex, dp,
                      charFrequency);

// Multiply the number of choices with getWords and add it to count.
countWays += charFrequency[wordsIndex][curPos] *
             getWords(words, target, wordsIndex + 1, targetIndex + 1, dp,
                      charFrequency);

return dp[wordsIndex][targetIndex] = countWays % 1000000007;

1. 문자를 선택하지 않는 경우:
   • 현재 위치를 건너뛰고 wordsIndex + 1로 이동.
2. 문자를 선택하는 경우:
   • charFrequency[wordsIndex][curPos]만큼 선택 가능.
   • 다음 target 문자로 진행.
3. 결과 저장:
   • 나머지 연산으로 오버플로우 방지.

---

시간 및 공간 복잡도

시간 복잡도

1. 빈도 계산:
   • $O(\text{words.size()} \times \text{words[0].size()})$.
2. DP 호출:
   • 각 상태를 한 번만 계산: $O(\text{words[0].size()} \times \text{target.size()})$.

총 시간 복잡도:
$O(\text{words.size()} \times \text{words[0].size()} + \text{words[0].size()} \times \text{target.size()})$

공간 복잡도

1. charFrequency: $O(\text{words[0].size()} \times 26)$.
2. dp: $O(\text{words[0].size()} \times \text{target.size()})$.

총 공간 복잡도:
$O(\text{words[0].size()} \times (\text{target.size()} + 26))$

---

작동 예시

입력:

words = ["acca","bbbb","caca"];
target = "aba";

계산 과정:

1. 빈도 계산: $\text{charFrequency} = \begin{bmatrix}[1, 0, 1], \\ [0, 1, 0], \\ [1, 0, 1], \\ [1, 1, 1] \end{bmatrix}$ (각 열은 a, b, c의 빈도를 나타냄).

2. DP 호출:

   • $dp[0][0]$: $3$ (3개의 방법 존재).

출력:

3

Approach 2: Bottom-up Dynamic Programming

• 76ms, 83.56MB
• Complexity
  • Let $totalWords$ be the total number of words in the words matrix, and $wordLength$ and $targetLength$ represent the length of any word in words and the target string, respectively.
  • Time Complexity: $O(\text{wordLength} \cdot \text{targetLength} + \text{wordLength} \cdot \text{totalWords})$
  • Space Complexity: $O(\text{wordLength} \cdot \text{targetLength})$

class Solution {
public:
    int numWays(vector<string>& words, string target) {
        int wordLength = words[0].size();
        int targetLength = target.size();
        const int MOD = 1000000007;

        // Step 1: Calculate frequency of each character at every index in
        // "words".
        vector<vector<int>> charFrequency(wordLength, vector<int>(26, 0));
        for (const string& word : words) {
            for (int j = 0; j < wordLength; ++j) {
                charFrequency[j][word[j] - 'a']++;
            }
        }

        // Step 2: Initialize a DP table.
        vector<vector<long>> dp(wordLength + 1,
                                vector<long>(targetLength + 1, 0));

        // Base case: There is one way to form an empty target string.
        for (int currWord = 0; currWord <= wordLength; ++currWord) {
            dp[currWord][0] = 1;
        }

        // Step 3: Fill the DP table.
        for (int currWord = 1; currWord <= wordLength; ++currWord) {
            for (int currTarget = 1; currTarget <= targetLength; ++currTarget) {
                // Carry over the previous value (not using this index of
                // "words").
                dp[currWord][currTarget] = dp[currWord - 1][currTarget];

                // Add ways using the current index of "words" if the characters
                // match.
                int curPos = target[currTarget - 1] - 'a';
                dp[currWord][currTarget] +=
                    (charFrequency[currWord - 1][curPos] *
                     dp[currWord - 1][currTarget - 1]) %
                    MOD;
                dp[currWord][currTarget] %= MOD;
            }
        }

        // Step 4: The result is in dp[wordLength][targetLength].
        return dp[wordLength][targetLength];
    }
};

GPT

이 코드는 문자열 배열 words에서 문자를 조합하여 문자열 target을 생성할 수 있는 방법의 수를 계산합니다. 이 접근 방식은 동적 프로그래밍(DP) 을 사용하며, 시간과 공간 효율성을 고려해 구현되었습니다.

---

문제 정의

1. 목표:
   • words 배열에서 각 단어의 동일한 위치에 있는 문자를 조합해 target 문자열을 생성.
   • $10^9 + 7$로 나눈 나머지를 반환.
2. 제약 조건:
   • $1 \leq \text{words.length}, \text{words[i].length}, \text{target.length} \leq 1000$.

---

코드 분석

1. 주요 아이디어

1. 문자 빈도 저장:
   • charFrequency[j][c]: words에서 인덱스 $j$에 위치한 문자 $c$의 빈도를 저장.
2. 동적 프로그래밍:
   • dp[i][j]: words의 첫 $i$개의 문자로 target의 첫 $j$개의 문자를 구성하는 방법의 수를 저장.
3. 점화식:
   • 현재 인덱스를 사용하지 않는 경우: dp[currWord][currTarget] = dp[currWord - 1][currTarget].
   • 현재 인덱스를 사용하는 경우: $dp[currWord][currTarget] += charFrequency[currWord - 1][target[currTarget - 1]] \times dp[currWord - 1][currTarget - 1]$

---

2. 코드 단계별 설명

Step 1: 문자 빈도 계산

vector<vector<int>> charFrequency(wordLength, vector<int>(26, 0));
for (const string& word : words) {
    for (int j = 0; j < wordLength; ++j) {
        charFrequency[j][word[j] - 'a']++;
    }
}

• charFrequency[j][c]는 words에서 인덱스 $j$에 위치한 문자 $c$의 빈도를 저장.
• 시간 복잡도: $O(\text{words.size()} \times \text{wordLength})$.

---

Step 2: DP 테이블 초기화

vector<vector<long>> dp(wordLength + 1, vector<long>(targetLength + 1, 0));
for (int currWord = 0; currWord <= wordLength; ++currWord) {
    dp[currWord][0] = 1;
}

• dp[i][0] = 1은 빈 문자열을 구성하는 방법의 수는 항상 1.
• DP 배열 크기:
  • 행: wordLength + 1 ($0$부터 시작).
  • 열: targetLength + 1 ($0$부터 시작).

---

Step 3: DP 테이블 채우기

for (int currWord = 1; currWord <= wordLength; ++currWord) {
    for (int currTarget = 1; currTarget <= targetLength; ++currTarget) {
        dp[currWord][currTarget] = dp[currWord - 1][currTarget];

        int curPos = target[currTarget - 1] - 'a';
        dp[currWord][currTarget] +=
            (charFrequency[currWord - 1][curPos] *
             dp[currWord - 1][currTarget - 1]) % MOD;
        dp[currWord][currTarget] %= MOD;
    }
}

• 현재 문자를 사용하지 않는 경우:
  • dp[currWord][currTarget] = dp[currWord - 1][currTarget].
• 현재 문자를 사용하는 경우:
  • 현재 문자 빈도(charFrequency[currWord - 1][curPos])와 이전 상태(dp[currWord - 1][currTarget - 1])를 곱하여 추가.
• 모듈러 연산:
  • $10^9 + 7$로 나머지를 구해 오버플로우 방지.

---

Step 4: 결과 반환

return dp[wordLength][targetLength];

• 최종 결과는 dp[wordLength][targetLength]에 저장.

---

시간 및 공간 복잡도

시간 복잡도

1. 문자 빈도 계산:
   $O(\text{words.size()} \times \text{wordLength})$.
2. DP 테이블 채우기:
   $O(\text{wordLength} \times \text{targetLength})$.

총 시간 복잡도:
$O(\text{words.size()} \times \text{wordLength} + \text{wordLength} \times \text{targetLength})$

공간 복잡도

1. charFrequency: $O(\text{wordLength} \times 26)$.
2. dp: $O(\text{wordLength} \times \text{targetLength})$.

총 공간 복잡도:
$O(\text{wordLength} \times (\text{targetLength} + 26))$

---

작동 예시

입력:

words = ["acca", "bbbb", "caca"];
target = "aba";

계산 과정:

1. charFrequency 계산: $\text{charFrequency} = \begin{bmatrix} [1, 0, 1], \\ [0, 1, 0], \\ [1, 0, 1], \\ [1, 1, 1] \end{bmatrix}$
   ($a, b, c$의 빈도).

2. DP 테이블 채우기:

   • 초기화: dp[i][0] = 1.
   • 점화식을 사용해 dp 채움.

3. 최종 결과:

   • dp[4][3] = 6 (6개의 방법 존재).

출력:

6

Approach 3: Optimized Bottom-up Dynamic Programmning

• 55ms, 32.68MB
• Complexity
  • Let $totalWords$ be the total number of words in the words matrix, and $wordLength$ and $targetLength$ represent the length of any word in words and the target string, respectively.
  • Time Complexity: $O(\text{wordLength} \cdot \text{targetLength} + \text{wordLength} \cdot \text{totalWords})$
  • Space Complexity: $O(\text{wordLength} \cdot \text{targetLength})$

class Solution {
public:
    int numWays(vector<string>& words, string target) {
        int wordLength = words[0].size();
        int targetLength = target.size();
        const int MOD = 1000000007;

        // Step 1: Calculate frequency of each character at every index in
        // "words".
        vector<vector<int>> charFrequency(wordLength, vector<int>(26, 0));
        for (const string& word : words) {
            for (int j = 0; j < wordLength; ++j) {
                charFrequency[j][word[j] - 'a']++;
            }
        }

        // Step 2: Initialize two DP arrays: prev and curr.
        vector<long> prevCount(targetLength + 1, 0);
        vector<long> currCount(targetLength + 1, 0);

        // Base case: There is one way to form an empty target string.
        prevCount[0] = 1;

        // Step 3: Fill the DP arrays.
        for (int currWord = 1; currWord <= wordLength; ++currWord) {
            // Copy the previous row into the current row for DP.
            currCount = prevCount;
            for (int currTarget = 1; currTarget <= targetLength; ++currTarget) {
                // If characters match, add the number of ways.
                int curPos = target[currTarget - 1] - 'a';
                currCount[currTarget] += (charFrequency[currWord - 1][curPos] *
                                          prevCount[currTarget - 1]) %
                                         MOD;
                currCount[currTarget] %= MOD;
            }
            // Move current row to previous row for the next iteration.
            prevCount = currCount;
        }

        // Step 4: The result is in prev[targetLength].
        return currCount[targetLength];
    }
};

GPT

이 코드는 문자열 배열 words에서 문자를 조합하여 문자열 target을 만들 수 있는 방법의 수를 계산합니다. 동적 프로그래밍(DP)을 사용하며, 공간 최적화를 통해 메모리 사용량을 줄인 방식입니다.

---

문제 정의

1. 주어진 입력:
   • words: 문자열 배열, 각 문자열의 길이는 동일.
   • target: 생성하려는 목표 문자열.
2. 목표:
   • words 배열에서 동일 위치에 있는 문자를 조합해 target 문자열을 만들 수 있는 방법의 수를 계산.
   • 결과를 $10^9 + 7$로 나눈 나머지를 반환.

---

코드 분석

1. 주요 아이디어

• charFrequency[j][c]: words에서 인덱스 $j$에 위치한 문자 $c$의 빈도를 저장.
• 공간 최적화된 동적 프로그래밍:
  • 두 개의 배열(prevCount, currCount)을 사용하여 DP 계산.
  • prevCount[j]: words의 앞 $i-1$개의 문자로 target의 첫 $j$개의 문자를 구성하는 방법의 수.
  • currCount[j]: 현재 currWord에서 갱신 중인 값.

---

코드 단계별 설명

1. 문자 빈도 계산

vector<vector<int>> charFrequency(wordLength, vector<int>(26, 0));
for (const string& word : words) {
    for (int j = 0; j < wordLength; ++j) {
        charFrequency[j][word[j] - 'a']++;
    }
}

• charFrequency[j][c] 는 words에서 인덱스 $j$에 위치한 문자 $c$의 빈도를 저장.
• 시간 복잡도: $O(\text{words.size()} \times \text{wordLength})$.

---

2. DP 배열 초기화

vector<long> prevCount(targetLength + 1, 0);
vector<long> currCount(targetLength + 1, 0);

// Base case: There is one way to form an empty target string.
prevCount[0] = 1;

• prevCount[j]는 현재까지 계산된 결과를 저장.
• currCount[j]는 현재 상태를 저장하며, 한 번의 루프 후에 prevCount로 복사.
• $j=0$: 빈 문자열을 구성하는 방법의 수는 항상 1.

---

3. DP 계산

for (int currWord = 1; currWord <= wordLength; ++currWord) {
    currCount = prevCount; // 이전 결과 복사
    for (int currTarget = 1; currTarget <= targetLength; ++currTarget) {
        int curPos = target[currTarget - 1] - 'a';
        currCount[currTarget] += (charFrequency[currWord - 1][curPos] *
                                  prevCount[currTarget - 1]) %
                                 MOD;
        currCount[currTarget] %= MOD;
    }
    prevCount = currCount; // 현재 결과를 이전 상태로 이동
}

작동 방식

1. 기존 값 복사:
   • currCount = prevCount: 현재 $j$번째 값을 이전 상태로 초기화.
2. 문자 매칭:
   • 현재 target 문자(target[currTarget - 1])와 words에서 해당 위치 문자가 일치하면 빈도에 따라 결과를 추가.
   • $dp[i][j] += \text{charFrequency[currWord - 1][target[currTarget - 1]]} \times dp[i-1][j-1]$.
3. 결과 갱신:
   • $MOD$로 나머지를 구해 오버플로우를 방지.
4. 다음 루프 준비:
   • prevCount를 currCount로 갱신.

---

4. 결과 반환

return currCount[targetLength];

• 최종 결과는 currCount[targetLength]에 저장.

---

시간 및 공간 복잡도

시간 복잡도

1. 문자 빈도 계산:
   $O(\text{words.size()} \times \text{wordLength})$.
2. DP 계산:
   $O(\text{wordLength} \times \text{targetLength})$.

총 시간 복잡도:
$O(\text{words.size()} \times \text{wordLength} + \text{wordLength} \times \text{targetLength})$

공간 복잡도

1. charFrequency:
   $O(\text{wordLength} \times 26)$.
2. prevCount, currCount:
   $O(\text{targetLength})$.

총 공간 복잡도:
$O(\text{wordLength} \times 26 + \text{targetLength})$

---

작동 예시

입력:

words = ["acca", "bbbb", "caca"];
target = "aba";

계산 과정:

1. charFrequency 계산: $\text{charFrequency} = \begin{bmatrix} [1, 0, 1], \\ [0, 1, 0], \\ [1, 0, 1], \\ [1, 1, 1] \end{bmatrix}$
   ($a, b, c$의 빈도).

2. DP 배열 갱신:

   • 초기화: prevCount[0] = 1.
   • $currWord = 1$: 업데이트된 값 계산.
   • $currWord = 2, 3, 4$: 반복 갱신.

3. 최종 결과:

   • $currCount[3] = 6$.

출력:

6