How to calculate time complexity?


  • 0
    S

    I came up with below code and it is a accepted solution. but i have a hard time to find out it time complexity.
    any one have any idea how to calculate its time complexity? (what if without the Dictionary memoery)

    PS: language C#

    public int NumDistinct (string s, string t)
    		{
    			if (string.IsNullOrEmpty (s) && string.IsNullOrEmpty (t))
    				return 1;
    			else if (string.IsNullOrEmpty (s) || string.IsNullOrEmpty (t))
    				return 0;
    
    			return FindSequences (s, 0, t, 0);
    		}
    
    		Dictionary<string, int> memoery = new Dictionary<string, int> ();
    
    		private int FindSequences (string s, int idxs, string t, int idxt)
    		{
    			if (idxt == t.Length)
    				return 1;
    			else if (idxs == s.Length)
    				return 0;
    			
    			string key = string.Format ("{0}-{1}", idxs, idxt);
    			if (memoery.ContainsKey (key))
    				return memoery [key];
    			
    			int result = 0;
    			if (s [idxs] == t [idxt]) {
    				result = FindSequences (s, idxs + 1, t, idxt + 1) + FindSequences (s, idxs + 1, t, idxt);
    			} else {
    				result = FindSequences (s, idxs + 1, t, idxt);
    			}
    			memoery.Add (key, result);
    			return result;
    		}

Log in to reply
 

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