akjuturub04
BAN USER// v1 and v2 are sorted vectors.
// value in nelem is valid only if return value is true
bool FindNthElement(vector<int>& v1, vector<int>& v2, int& nelem, int rank)
{
bool ret = false;
int n1 = v1.size(), n2 = v2.size();
int size = n1+n2;
int i=0,j=0,k=0, count = 0, temp;
if( (rank <= size) && (rank>0) )
{
while( (k<size) && (count!=rank ) )
{
if( (i<n1) && (j<n2) )
{
if( v1.at(i) <= v2.at(j) )
{
temp = v1.at(i); i++;
}
else
{
temp = v2.at(j); j++;
}
}
else if(i<n1)
{
temp = v1.at(i); i++;
}
else
{
temp = v2.at(j); j++;
}
nelem = temp; count++;
if( count == rank )
{
ret = true;
}
k++;
}
}
return ret;
}
Please let me know if you my code gives a wrong result. :)
I see that you have used dynamic programming which is O(m*n). I think we can solve the problem in O(m).
m - length of longer string. n - length of shorter string.
int diffcount(string& s1, string& s2, int begin1, int begin2, int n)
{
int ret = 0;
int i = 0;
for(i=0; i<n; i++)
{
if( s1.at(begin1+i) != s2.at(begin2+i) )
{
ret++;
}
}
cout<<" diffcount: "<<ret<<"\n";
return ret;
}
bool IsEditDistanceOne(string& s1, string& s2)
{
bool ret = false;
int n1 = s1.length(), n2 = s2.length();
if ( n1 == n2 )
{
ret = ( diffcount(s1,s2,0,0,s1.length()) == 1 );
}
else
{
int count = 0;
string *one = &s1, *two = &s2;
if( n2>n1 )
{
one = &s2; two = &s1;
}
int i = 0;
while( (i<two->length() ) && (count<2) )
{
if( one->at(i+count) == two->at(i) )
{
i++;
}
else
{
count++;
}
}
ret = (count==1);
}
return ret;
}
This should solve the problem in O(n). Please let me know if you find any problems with this code. :)
- akjuturub04 November 20, 2014
@imps I do consider the of insertion and deletion. Can you probably give me an example where my code fails. For example, I tested on strings like "sport" and "sort" and my code gave me an edit distance of one.
- akjuturub04 November 21, 2014