Vishap
BAN USERIf I get this right this is an O(n*log(d)) solution, where d is the size of dictionary.
typedef std::vector<std::string> dict_t;
int lower_bound(const dict_t& d, int b, int e, int c, int p)
{
while( b < e ){
int m = (b+e)/2;
if ( d[m].length() < p || d[m][p] < c )
b = m+1;
else
e = m;
}
return b;
}
int upper_bound(const dict_t& d, int b, int e, int c, int p)
{
while( b < e ){
int m = (b+e)/2;
if ( d[m].length() < p || d[m][p] <= c )
b = m+1;
else
e = m;
}
return b;
}
std::unordered_set<int> memo;
bool word_search( const dict_t& d, const std::string& s, int w =0 )
{
if ( memo.find(w) != memo.end() )
return false;
int l = s.length();
int b = 0;
int e = d.size();
for ( int i = w; i < l; ++i ) {
b = lower_bound(d, b, e, s[i], i-w);
e = upper_bound(d, b, e, s[i], i-w);
if ( b >= e ) {
memo.insert(w);
return false;
}
else if ( d[b].length() == i-w+1
&& ( i+1 >= l
|| word_search( d, s, i+1 ) ) ) {
return true;
}
}
memo.insert(w);
return false;
}
Let's say my vector is a={1, 2, 3, 4} and K=8. Then all non empty subsets do satisfy the condition, therefore the answer should be 15 in this case. But the algorithm will produce 14. The reason is that when the algorithm considers j==3 case, it assumes that the set {2, 3} was already counted, but it was not.
If we move int max_interval_ending = 0; inside the loop, then that will not work either. In the case above it will produce more than 16. So perhaps we need to move also int num_valid_subsets = 0; inside the loop and then calculate sum of all num_valid_subsets?
But then the following example will not produce proper result I guess a={1, 2, 9, 3, 4} and K=8.
However, the idea is an interesting one. I came up with this solution:
- Vishap March 06, 2019