Stringsort -using STL

#1

Nishant is a very naughty boy in Launchpad Batch. One day he was playing with strings, and randomly shuffled them all. Your task is to help Nishant Sort all the strings ( lexicographically ) but if a string is present completely as a prefix in another string, then string with longer length should come first. Eg bat, batman are 2 strings and the string bat is present as a prefix in Batman - then sorted order should have - Batman, bat.

Input Format:
N(integer) followed by N strings.

Constraints:
N<=1000

Output Format
N lines each containing one string.

Sample Input
3
bat
apple
batman
Sample Output
apple
batman
bat


i am failing one testcase please guide me.

#2

i m also stuck in the same problem, 1 test case passed.
but i am using substring, try using substring may be u’ll come up with a solution…

#3

#include
#include
#include
#include

using namespace std;

bool compare(string a,string b)
{
string r = a.substr(0,b.length());
transform(r.begin(),r.end(),r.begin(), ::tolower);
if(r==b)
{
return a>b;
}
r= b.substr(0,a.length());
transform(r.begin(),r.end(),r.begin(), ::tolower);
if(r==a)
{
return b>a;
}
else
{
return a<b;
}
}

int main() {
vector v;
int n,i;
cin>>n;
for(i=0;i<=n;i++)
{
string w;
getline(cin,w);
v.push_back(w);
}
sort(v.begin(),v.end(),compare);
for(i=0;i<=n;i++)
{
cout<<v[i]<<"\n";
}
return 0;
}

1 Like
#4

Akash bro can you explain your compare function because my compare function is of only four lines and it passes all the test cases.

#5

Hi saumya,
can you please share your code

#6

/##############################################################################
AUTHOR : RAGHAV GUPTA
DATE : 23 May 2019
AIM : sort n strings lexicographically but if two strings have a common beginning
then the bigger string should come first
STATUS : !!! success !!! according to portal
but …
according to me the output should be more refined later on
##############################################################################/
#include
#include
#include
using namespace std;

bool comparator(string s1, string s2){
if(s1[0]==s2[0]) // if first character is same, then sort according to length
return s1.length() > s2.length();
else // else sort lexicographically
return s1<s2;
}

int main(){

int n; // number of strings
cin>>n;

string str[n]; // string array

for(int i=0; i<n; i++){ // input strings
cin>>str[i];
}

sort(str, str+n, comparator);

for(int i=0; i<n; i++){ // display sorted strings
cout<<str[i]<<endl;
}

return 0;
}

1 Like
#7

this is my code. its not perfect according to me but the test cases designed are not appropriate, so it works.

#8

I hope it helps.
#include
#include
#include
using namespace std;

bool compare(string s, string s1){
 if(s[0]==s1[0])
    return s.length()>s1.length(); // descending order.
 else
   return s<s1; // ascending order.
}
int main() {
	int n;
    cin>>n;
    string s;
    string str[n];
    for(int i=0;i<n;i++){
        cin>>s;
        str[i]=s;
    }
    sort(str,str+n,compare);
    for(int i=0;i<n;i++){
        cout<<str[i]<<endl;
    }
}
1 Like
#9

but what if the input is
2
bate
batman

#10

whats wrong with this code…
#include<bits/stdc++.h>
using namespace std;
bool comp(string a,string b)
{
if(a[0]==b[0])
{
return (a.length()>b.length());

}
return a<b;

}
int main() {
int n;
cin>>n;
string s1[n];
for(int i=0; i<n; i++)
{
string s;
cin>>s;
s1[i]=s;
}

sort(s1,s1+n,comp);
for(int i=0; i<n; i++)
cout<<s1[i]<<endl;
return 0;

}

#11

one test case not working

#12

i think bate in not prefix of batmen

#13

My Approach for the problem:
import java.util.;
class CompareString implements Comparator{
public int compare(Sort obj1,Sort obj2){
if(obj1.getString().contains(obj2.getString())){
return obj1.getString().compareTo(obj2.getString())(-1);
}
return obj1.getString().compareTo(obj2.getString());
}
}
class Sort {
private String str;
public Sort(String str){
this.str=str;
}
public void setString(String str){
this.str=str;
}
public String getString(){
return this.str;
}
}
public class Main {
public static void main(String args[]) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
ArrayList al=new ArrayList<>();
for(int i=0;i<n;i++){
String str=input.next();
al.add(new Sort(str));
}
Collections.sort(al,new CompareString());
for(int i=0;i<n;i++){
System.out.println(al.get(i).getString());
}

  }
}
#14

#include<bits/stdc++.h>
using namespace std;

bool comparator(string s1, string s2)
{
if(s1==s2.substr(0,s1.length()) || s2==s1.substr(0,s2.length())) // if first character is same, then sort according to length
return s1.length() > s2.length();
else // else sort lexicographically
return s1<s2;
}

int main()
{
int n; // number of strings
cin>>n;

string str[n]; // string array

for(int i=0; i<n; i++)
{ // input strings
	cin>>str[i];
}

sort(str, str+n, comparator);

for(int i=0; i<n; i++)
{ // display sorted strings
	cout<<str[i]<<endl;
}
return 0;

}

#15

#include<bits/stdc++.h>
using namespace std;
bool cmp(string s1,string s2){
if(s1[0]!=s2[0]){
return s1<s2;
}
int i=0;
while(s1[i]==s2[i]){
i++;
}
if(i==s1.length()|| i==s2.length()){
return s1.length()>s2.length();
}
return s1<s2;

}
int main() {
int n;
cin>>n;
vectorv(n);
for(int i=0;i<n;i++)
cin>>v[i];

sort(v.begin(),v.end(),cmp);
for(auto x:v){
	cout<<x<<endl;
}
return 0;

}

1 Like