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