Why getting tle? word break problem gfg

Revision en1, by coder_of_india., 2021-12-04 19:53:11
#include <bits/stdc++.h>
using namespace std;

struct Node
{

vector<Node*> child ;
bool is ;

Node()
{
child.resize(26 , NULL) ;
is = false;
}

};

class Trie{

Node *root ;

public:
Trie()
{
root = new Node() ;
}

void insert(string s)
{

Node *cur = root ;
int i = 0 ;
while(i < s.length())
{
if(cur -> child[s[i] - 'a'] == NULL)
cur -> child[s[i] - 'a'] = new Node();

cur = cur -> child[s[i] - 'a'] ;
i ++ ;
}

cur -> is = true ;
}

void search(string &s ,int st , vector<bool> &dp)
{
Node *cur = root ;
for(int i = st ; i < s.length() ; i ++ )
{

if(cur == NULL)
return  ;
cur = cur -> child[s[i] - 'a'] ;

if(cur && cur -> is )
dp[i + 1] = true ;
}

}
};
class Solution{
public:

int wordBreak(string A, vector<string> &B) {
//code here
Trie *tmp = new Trie();
int n = A.size() ;

vector<bool> dp(n + 1, false) ;

for(int i =0 ; i < B.size() ; i ++ )
tmp -> insert(B[i]) ;

dp[0] = true ;
for(int i = 0 ; i < A.length() ; i ++ )
{
if(dp[i])
tmp -> search( A , i , dp) ;

}

return dp[n];
}

};
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<string> dict;
for(int i=0;i<n;i++){
string S;
cin>>S;
dict.push_back(S);
}
string line;
cin>>line;
Solution ob;
cout<<ob.wordBreak(line, dict)<<"\n";
}
}



#### History

Revisions

Rev. Lang. By When Δ Comment
en3 coder_of_india. 2021-12-05 07:59:16 9
en2 coder_of_india. 2021-12-04 19:53:54 17
en1 coder_of_india. 2021-12-04 19:53:11 2124 Initial revision (published)