Given n strings in any order. Sort all the strings (lexicographically), but if a string is present completely as a prefix in another string, then string with larger length should come first.
Examples:
Input : 3 cap apple captain Output : apple captain cap Explanation: cap is present in captain as a prefix, so string : captain being larger in length then cap, so captain will come before cap.
Approach:
Using sort STL function with a bool comparator to apply for given condition.
If a string is present as a prefix in another string, then larger string should be printed first.
Find function to check for occurrences of one string in another.
Using npos : is a static member constant value with the greatest possible value for an element of type size_t.
Implementation in C++:
#include <iostream>
#include <algorithm>
#include <cstring>
#define ull unsigned long long int
using namespace std;
bool mycompare(string a, string b)
{
// Checking if either of string
// a or b is prefix of another
if ((a.find(b) != string::npos) || (b.find(a) != string::npos))
{
// If present, returning that string
// with larger length
return a.length() > b.length();
}
return a < b;
}
int main()
{
int n = 3;
string str[] = { "bat", "ball", "batsman" };
// STL function for string sorting
// with custom comparator (mycompare)
sort(str, str + n, mycompare);
for (int i = 0; i < n; i++)
cout << str[i] << endl;
return 0;
}
Output:
ball batsman bat