C# : Don't Know why it is a TLE, even though time taken is 292 ms


  • 0
    J

    Here is my solution:

    For inputs:
    "ngsmeascnjzocuongsrfaxguyimfutgiwufuhjjqbtmzjyflpstnnuacztbmkvjibxbbcsqxubyasjfzodygfdxbihmmykmonrzejsarwcxlbeztserbmhgybiqxbyfmgrlnnvigicnrutzdqufmnpjsepbvrzgayuxkpfolsrnvoarvgbpdrklzzzogrhdyrmrjxwoudlinnbhkwnsqkwdrfyqgmpppgepkxifwdehpitvpzbamohkzysjxkssempyhxmhyebsiigqbrrvhfuweimkfnixymotoaksgrbradaxwbo"
    "enfrngmgdnmgvibmdqonhtnkmnaherhspkohhtebejvboyvkoderpgkusslomowuybsijwjjqzwxlbhmnwqwchxvnnsinnmxhvktslvagjralxfihmppbkxslvmgvotgkjxbuhekvixrkxdcbidpprfsofhlcsdwxnvbdsxtlfskqyfnpipgpoyepfwigpmlzutgqpcowgdsdudxsnfyoustbwquqavmcqmupzyxtbajprtxjzgcoxqgsowcjpedmrquyywnxccfedzt"

    public int MinimumDeleteSum(string s1, string s2) {
           if (string.IsNullOrEmpty(s1) || string.IsNullOrEmpty(s2))
                {
                    return 0;
                }
                var dic = new Dictionary<string, int>();
    
                return DFS(s1, s2, 0, 0, 0, dic);
        }
        
        public int DFS(string s1, string s2, int i, int j, int cost, Dictionary<string, int> keys)
        {
               var key = (i + "," + j).ToString();
    
                if (keys.ContainsKey(key))
                {
                    return cost + keys[key];
                }
    
                int cur = 0;
    
                if (i == s1.Length)
                {
                    for (int k = j; k < s2.Length; k++)
                    {
                        cur += (int)s2[k];
                    }
    
                    keys.Add(key, cur);
                    return cur + cost;
                }
    
                if (j == s2.Length)
                {
                    for (int k = i; k < s1.Length; k++)
                    {
                        cur += (int)s1[k];
                    }
    
                    keys.Add(key, cur);
                    return cur + cost;
                }
    
                if (s1[i] != s2[j])
                {
                    int c1 = DFS(s1, s2, i + 1, j, (int)s1[i], keys);
                    int c2 = DFS(s1, s2, i, j + 1, (int)s2[j], keys);
    
                    keys.Add(key, Math.Min(c1, c2));
                    return cost + (Math.Min(c1, c2));
                }
                else
                {
                    var s = (DFS(s1, s2, i + 1, j + 1, 0, keys));
                    keys.Add(key, s);
                    return cost + s;
                }
        }
    

  • 0
    S

    @jainchethan87 said in C# : Don't Know why it is a TLE, even though time taken is 292 ms:

    key

    maybe you can use a two dimension array to cache the result


  • 0
    J

    @saddays
    I figured out eventually to use a matrix to store intermediates results.
    But my question is runtime is <300 ms, and I remember having certain test cases take more than that, but still would pass.
    I don't know what the timing reqs are.


Log in to reply
 

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