If strings do not have same lengths, this simple greedy algorithm does not
work. E.g.
b
ba
bab
The best answer is bababb, instead of bbabab.
A correct way is to define a new string comparison operator, and concatenate
strings in that order:
bool comp(const string &a, const string &b)
{
return a + b < b + a;
}
2011/2/17 Wladimir Tavares <[email protected]>
> My one cent:
>
> I think one greedy approach solve thus if you only sort the array of string
> and then concatenate follow the order
>
>
> Wladimir Araujo Tavares
> *Federal University of Ceará
>
> *
>
>
>
>
>
> On Thu, Feb 17, 2011 at 12:05 AM, simplyamey
> <[email protected]>wrote:
>
>> Try this code.
>>
>> #include<iostream>
>> #include<string>
>> using namespace std;
>> int main()
>> {
>> string sArray[5] ={"aab","abc","bba","acc","bcc"};
>>
>> int n = 5;
>>
>> for(int i = 0;i < n; i++)
>> {
>> for( int j = 0; j < n - 1 ; j++)
>> {
>> if(sArray[j] > sArray[j+1])
>> {
>> string temp = sArray[j];
>> sArray[j] = sArray[j + 1];
>> sArray[j+1]= temp;
>> }
>> }
>> }
>>
>> string sTemp;
>> for(int k = 0; k < n ;k++)
>> {
>> sTemp = sTemp + sArray[k];
>> }
>> cout<<"printing result::"<< sTemp<<endl;
>> }
>>
>> n = Number of strings.
>>
>> On Feb 17, 9:56 am, bittu <[email protected]> wrote:
>> > Given a group of strings, find a string by concatenating all the
>> > strings in any order which produces the lexicographically smallest
>> > string.
>> > For e.g strings are acc bcc abb
>> > So the string formed should be abbaccbcc
>> >
>> > Thanks
>> > Shashank
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
此致
敬礼！
林夏祥
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
