3291. Minimum Number of Valid Strings to Form Target I | Weekly Leetcode 415

[@varungudamsetti449]

Why cant we just store all the prefixes in a set and have a constant time lookup in the recursive method? In that case TC would be tLen*tLen right? I did the same but it is giving me TLE. Could you please explain why?

[@codingmohan]

Inside the for loop you would be doing something like -
allPrefixesSet.count(prefix)
This is not O(1) operation because for just 1 comparison you would need to iterate over the string. Hence your current complexity is T*T*T.
To make this approach work, you would need to hash all your stored prefixes and store the hash in the set.
Now while comparing, you will hash the prefix (rolling hash) and search that in the set.

[@shreyanshkumarsahu6534]

I also use set for storing prefixes but get MLE

[@lambukushireddy424]

Nice explanation

[@satyamraj2779]

thanks for making credible editorials.

[@arjunc1482]

Can you do the drawing in dark mode?

[@guruharsha6275]

Can u post solutions yesterday's biweekly contests hard questions?

[@codingmohan]

Here you go - th-cam.com/video/ea9Kjfc9ZzI/w-d-xo.html

[@guruharsha6275]

@@codingmohanand the 4th one?

[@Abhi_008]

what if i could generate all the prefixes of given string and store it in set.
Then Iterate over target checking if 1,2,3, ... lengths of prefixes are available in set. If yes, then we make reursive call for further length 1,2,3....
This also has an T^2 complexity but giving tle on 916/929?
sudo code:
int res = INT_MAX;
string prefix;

for (int j = idx; j < n; j ++) { // iterating over target string
prefix += target[j];
if (st.count(prefix)) { // checking in set if prefix are available
int nextRec = optimal(words, target, j + 1);
if (nextRec != -1) {
res = min(res, 1 + nextRec);
}
} else break;
}

[@varungudamsetti449]

I did exactly the same and my doubt is also the same.

[@Abhi_008]

@@varungudamsetti449 But dont know why tle? since the time complexity remains only T^2. Right??

[@codingmohan]

I tried explaining in another comment above (see the pinned comment).

[@NAMANSINGH-d2z]

trie dp keeps giving me mle,can you tell what further optimistion is needed in my case
struct Node{
Node *links[26];
bool end = false;
bool containsKey(char ch)
{
return links[ch - 'a'] != NULL;
}
void put(char ch,Node* node)
{
links[ch - 'a'] = node;
}
Node* get(char ch)
{
return links[ch - 'a'];
}
bool isEnd()
{
return end;
}
void setEnd()
{
end = true;
}
};
class Trie {
Node* root;
public:
Trie() {
root = new Node();
}

void insert(string word) {
Node* node = root;
for(int i = 0; icontainsKey(word[i]))
{
node->put(word[i],new Node());
}
node = node->get(word[i]);
}
node->setEnd();
}

bool prefix(string prefix) {
Node* node = root;
for(int i = 0; icontainsKey(prefix[i]))
{
return false;
}
node = node->get(prefix[i]);
}
return true;
}
};
class Solution {
public:
int n,m;
// int dp[5005];
Trie* trie = new Trie();
int solve(vector& words, string& target,int idx,vector& dp)
{
if(idx >= n) return 0;
if(dp[idx]!=-1) return dp[idx];
int res = 1e9;
for(int i = idx; iprefix(temp)) res = min(res,1+solve(words,target,i+1,dp));
}
return dp[idx] = res;
}
int minValidStrings(vector& words, string target) {
m = words.size();
n = target.size();
for(int i = 0; iinsert(words[i]);
// memset(dp,-1,sizeof dp);
vector dp(n+1,-1);
int res = solve(words,target,0,dp);
return res == 1e9 ? -1 : res;

}
};

[@codingmohan]

You are finding out the "temp" and then iterating over it again (using trie) to get the answer. Hence inside the outer for loop (of idx), you have a hidden for loop which will also run for upto a size of T. Therefore making complexity of single state as T×T in worst case.
You can optimize the hidden loop by reusing the iterations done in previous steps. For example, notice that the new "temp" is simply having 1 more character than the previous one. Hence you can persist the trie node you reached in previous iteration and simply continue 1 more step from there.
Something like -
temp_root = trie->root
for I in (idx, n):
temp_root = temp_root->get(targeti)
....

[@NAMANSINGH-d2z]

​@@codingmohan thanks for this, i was not able to think about the hidden loop. The idea of using previous node is great, i am sure it will help in future also, thanks

[@sanjanaaa17]

@@NAMANSINGH-d2z can you share your accepted code?