Why I'm getting tle please help ? word break problem gfg ........

Revision en3, by coder_of_india., 2021-12-05 07:59:16


#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 English coder_of_india. 2021-12-05 07:59:16 9
en2 English coder_of_india. 2021-12-04 19:53:54 17
en1 English coder_of_india. 2021-12-04 19:53:11 2124 Initial revision (published)