Today I was solving the word break problem but I was not able to calculate the time complexity of the implemented solution.
Here is the question:-
https://practice.geeksforgeeks.org/problems/word-break-part-2/0/
We have to find and print every sentence formed by the given string from the words contained in the dictionary provided in the test case.
My solution:-
#include<bits/stdc++.h>
using namespace std;
set<vector<string>> res;
vector<string> v;
void Print_Vector(vector<string> Vec){
cout << "(";
for(int i = 0 ; i < Vec.size() ; i++){
if(i == Vec.size() - 1)
cout << Vec[i];
else
cout << Vec[i] << " ";
}
cout << ")";
}
void helper(string& s, unordered_set<string>& st, int i){
if(i == s.size()){
res.insert(v);
return;
}
string temp = "";
for(int k = i ; k < s.size() ; k++){
temp += s[k];
if(st.find(temp) != st.end()){
v.push_back(temp);
helper(s, st, k+1);
v.pop_back();
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
unordered_set<string> st;
string s;
for(int i = 0 ; i < n ; i++){
cin >> s;
st.insert(s);
}
cin >> s;
res.clear();
v.clear();
helper(s, st, 0);
for(auto it = res.begin() ; it != res.end() ; it++)
Print_Vector(*it);
cout << endl;
}
}