~~~~~↵
↵
↵
#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";↵
}↵
}↵
↵
~~~~~↵
↵
↵
↵
#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";↵
}↵
}↵
↵
~~~~~↵
↵
