<Hard> Distinct Subsequences (LeetCode : C#)

https://leetcode.com/problems/distinct-subsequences/

📕 문제 설명

두 문자열이 주어질 때 s의 subsequence로 t를 만들 수 있는 개수 반환

• Input
  두 문자열 s, t
• Output
  s의 distinct한 subsequence로 t를 만들 수 있는 개수

예제

실패 (시간 초과)
문자 별로 index 저장해두고 t 순회하면서 현재 문자에서 보고 있는 인덱스 기준 그 다음 문자가 현재 index 보다 커야만 그 다음 케이스 보는 방식

public class Solution {
    Dictionary<char, List<int>> indexDict; 
    string targetString;
    public int NumDistinct(string s, string t) {
        indexDict = new Dictionary<char, List<int>>();
        targetString = t;
        for(int i = 0; i < s.Length; i++)
        {
            if (indexDict.TryGetValue(s[i], out List<int> indexList))
            {
                indexList.Add(i);
            }
            else
            {
                indexDict.Add(s[i], new List<int>() {i});
            }
        }

        foreach(char c in t)
        {
            if (!indexDict.TryGetValue(c, out List<int> indexList)) return 0;
        }

        if (t.Length == 1) return indexDict[t[0]].Count;
        
        List<int> firstCharIndexList = indexDict[t[0]];
        int answer = 0;
        foreach(int index in firstCharIndexList)
        {
            answer += GetSubsequenceCount(index, 0);
        }

        return answer;
        
    }

    public int GetSubsequenceCount(int minIndex, int tIndex)
    {
        int count = 0;
        bool isLast = tIndex + 1 == targetString.Length - 1;
        List<int> charIndexList = indexDict[targetString[tIndex + 1]];

        foreach(int index in charIndexList)
        {
            if (index > minIndex)
            {
                if (isLast) count++;
                else
                {
                    count += GetSubsequenceCount(index, tIndex + 1);
                }
            }
        }

        return count;
    }
}

실패 2 (시간 초과)
아까 위에서 동일하게 사용되는 데이터 저장해서 불러오는 식으로 변경
(시간 좀 더 나아지긴 함)

public class Solution {
    Dictionary<char, List<int>> indexDict; 
    Dictionary<(int, int), int> dpDict;
    string targetString;
    public int NumDistinct(string s, string t) {
        indexDict = new Dictionary<char, List<int>>();
        dpDict = new Dictionary<(int, int), int>();
        targetString = t;
        for(int i = 0; i < s.Length; i++)
        {
            if (indexDict.TryGetValue(s[i], out List<int> indexList))
            {
                indexList.Add(i);
            }
            else
            {
                indexDict.Add(s[i], new List<int>() {i});
            }
        }

        foreach(char c in t)
        {
            if (!indexDict.TryGetValue(c, out List<int> indexList)) return 0;
        }

        if (t.Length == 1) return indexDict[t[0]].Count;
        
        List<int> firstCharIndexList = indexDict[t[0]];
        int answer = 0;
        foreach(int index in firstCharIndexList)
        {
            answer += GetSubsequenceCount(index, 0);
        }

        return answer;
        
    }

    public int GetSubsequenceCount(int minIndex, int tIndex)
    {
        int count = 0;
        bool isLast = tIndex + 1 == targetString.Length - 1;
        List<int> charIndexList = indexDict[targetString[tIndex + 1]];

        foreach(int index in charIndexList)
        {
            if (index > minIndex)
            {
                if (isLast) count++;
                else
                {
                    if (!dpDict.TryGetValue((index, tIndex + 1), out int cnt))
                    {
                        dpDict[(index, tIndex + 1)] = GetSubsequenceCount(index, tIndex + 1);
                    }
                    
                    count += dpDict[(index, tIndex + 1)];
                }
            }
        }

        return count;
    }
}

풀이

DP 사용 (이전 풀이에 빠져서 이렇게 접근하는데 한참 걸렸다..)
점화식 : dp[i][j]
t[0~j]와 동일한 s[0~i]의 subsequence 수

다음 케이스에 따라 나뉜
case1) s[i] == t[j]
현재 보는 문자가 같으면 바로 이전 문자 기준 가능했던 subsequence에다가 현재 보는 문자의 가능한 케이스를 더해주면 된다.
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

case2) s[i] != t[j]
다른 경우 갱신되지 않기 때문에 이전 값 그대로 들고온다.
dp[i][j] = dp[i-1][j]

public class Solution {
    public int NumDistinct(string s, string t)
    {
        var dp = new int[s.Length + 1, t.Length + 1];
        for (var i = 0; i <= s.Length; i++)
        {
            dp[i, 0] = 1;
        }

        for (var i = 1; i <= s.Length; i++)
        {
            for (var j = 1; j <= t.Length; j++)
            {
                if (s[i - 1] == t[j - 1])
                {
                    dp[i, j] = dp[i - 1, j - 1] + dp[i - 1, j];
                }
                else
                {
                    dp[i, j] = dp[i - 1, j];
                }
            }
        }

        return dp[s.Length, t.Length];
    }
}

결과