just another LCS problem


  • 0
    S

    step1: find LCS between S and T by using DP
    step2: if the length of LCS is equal to length of T, read the LCS

    public class Solution {
        public string MinWindow(string S, string T) {
            var dp = new int[S.Length + 1, T.Length + 1];
            var res = string.Empty;
            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] + 1;
                        if (dp[i, j] == T.Length)
                        {
                            var t = ReadLcs(dp, S, T, i, j);
                            if (t.Length < res.Length || string.IsNullOrEmpty(res))
                                res = t;
                        }
                    }
                    else
                        dp[i, j] = Math.Max(dp[i-1, j], dp[i, j-1]);
                }
            
            return res;
        }
        
        private string ReadLcs(int[,] dp, string S, string T, int i, int j)
        {
            var k = 0;
            var right = i;
            while (k < T.Length)
            {
                if (S[i-1] == T[j-1])
                {
                    i--;
                    j--;
                    k++;
                }
                else if (dp[i-1, j] > dp[j, j-1])
                    i--;
                else
                    j--;
            }
            return S.Substring(i, right - i);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.