Hello world! Can you help me with this(Word break) problem's time complexity. Actually I always feel difficulty in finding time complexity of memoization solutions.
Below is my accepted code:
class Solution {
public:
int solve(string s, vector<vector<string>> &v, int i, vector<int> &dp)
{
if(i==s.size())
{
return 1;
}
if(dp[i]!=-1)
return dp[i];
char c=s[i];
if((int)v[c-'a'].size()==1)
{
return 0;
}
else
{
int x=0;
for(int j=0;j<(int)v[c-'a'].size()-1;j++)
{
if(s.substr(i, (int)v[c-'a'][j].size())==v[c-'a'][j])
{
x|=solve(s, v, i+(int)v[c-'a'][j].size(), dp);
}
}
dp[i]=x;
return x;
}
}
bool wordBreak(string s, vector<string>& wordDict) {
int n=s.size();
vector<vector<string>> v(26);
for(int i=0;i<wordDict.size();i++)
{
char c=wordDict[i][0];
v[c-'a'].push_back(wordDict[i]);
}
for(int i=0;i<26;i++)
v[i].push_back("x");
vector<int> dp(n+1, -1);
return solve(s, v, 0, dp);
}
};
Thank u.
It tend to be $$$O(|s| + |wordDict| + 26)$$$ = Linear time&space complexity since there is only a simple loop, 1D-array initialization, and the function is not recursive.
When you face to memorization complexity, there is a kind of upper bound that $$$O(f(x) \times g(x))$$$ where $$$O(f(x))$$$ is maximum number of states and $$$O(g(x))$$$ is the maximum cost of changing state. In your code is $$$O(f(x) \times g(x)) = O(O(|s| + |wordDict| + 26) \times O(1)) = O(N)$$$