What is the time complexity of my algorithm?


  • 0
    W
    bool wordBreak(string s, unordered_set<string> &dict) {
     /* index[i] indicates the current max index of string s[0..i] that can be matched of the 
     combination of the words in the dictionary */
    	int *index = new int[s.length()+1];
    	index[0] = 0;
    	for(int i = 1;i <= s.length();i++)
    	{
    		for(int j = 0;j<i;j++)
    		{
    			string temp;
    			temp = s.substr(index[j],i-index[j]);
    			if(dict.find(temp)!=dict.end())
    			{
    				index[i] = i;//record the match index
    				break;
    			}
    			else
    			{
    				index[i] = index[i-1];//when not match,just copy the last index
    			}
    		}
    	}
    
    	if(s.length() == index[s.length()])
    		return true;
    	else
    		return false;
    }
    

    Is this algorthim good enough? I'm not sure of its time complexity. Hope someone can give me some help.


  • 0
    J

    In the worst case when there is no match in the dict, the time complexity is O(n^2).

    In addition, I understand that

     temp = s.substr(index[j],i-index[j]);
    

    temp is only meaningful when index[j] == j.


Log in to reply
 

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