abhiV
BAN USERA dp solution I can think of is:
iterate through string, at each character determine if it completes a match or adds to a match. If it completes a match, save the Indexes (use it display later on). If it adds to an incomplete match save indexes in a separate data structure to use in the case that a later character completes the match. T = O(n^2)
void findDiscontinuousMatches(string s, string p, int slength, intplength)
{
if(slength == 0 || plength == 0 || plength > slength)
return null;
list<string> incompleteMatches;
vector<vector<int>> incompleteIndices;
vector<vecotr<int>> completeIndices;
incompleteMatches.push_front("");
vector<int> placeHolder v;
incompleteIndices.push_back(v);
for(int i = 0; i<slength; i++)
{
auto it2 = incompleteIndices.begin();
for(auto it = incompleteMatches.begin(); it != incompleteMatches.end(); it++)
{
if(it2 = incompleteIndices.end())
break;
//completes a match
if( (it->first + s[i]).equals(p) )
{
vector<int> completedIndex (it2->first);
completedIndex.push_back(i);
completeIndices.push_back(completedIndex);
}
//adds to an incomplete match
if( p.startsWith(it->first + s[i]) )
{
incompleteMatches.push_front(it->first + s[i]);
vector<int> incompleteIndex (it2->first);
incompleteIndex.push_back(i);
completeIndices.push_back(incompleteIndex);
}
it2++;
}
}
printDiscontinuous(s, completeIndices); //Didn't write this method
}
Using quickselect method (i.e. partition method of quick sort) average time is n. However, worst case time is O(n^2).
- abhiV June 28, 2015