CareerCup

list.sort(Comparator.naturalOrder())

We can use Java inbuilt function compateTo(comparableString) and achieve this with n2 complexity. Below is a sample code snippet.

for(int i=0;i<=s.length-2;i++)
        {
            System.out.println(s[i]);
            for(int j=i+1;j<=s.length-1;j++)
            {
                
                if(s[i].compareTo(s[j])>0)
                {
                    String temp = s[j];
                    s[j]=s[i];
                    s[i]=temp;
                }
            }
        }

Java inbuilt function compareTo will work but with n2 complexity

for(int i=0;i<=s.length-2;i++)
{
System.out.println(s[i]);
for(int j=i+1;j<=s.length-1;j++)
{

if(s[i].compareTo(s[j])>0)
{
String temp = s[j];
s[j]=s[i];
s[i]=temp;
}
}
}

Method 1: use general sorting algorithm Complexity: O(nlogn)
Method 2: use Trie data structures O(n)

Can you someone help me how to get this using Trie DS. I have given all the above solutions but interviewer asked me to implement using Trie DS.

Can anyone one help me solve this using Trie DS. I have given all the above solutions but interviewer asked me to implement using Trie.

import java.util.Arrays;

public class StringSort {

public static void main(String[] args) {

String abc[]= {"ABCDEF","A","BEF","AABB","AA"};
Arrays.sort(abc);
for(int i=0;i<abc.length;i++)
{
System.out.println(abc[i]);
}

}

}

public class PrintInLexicographicOrder {
    public static void main(String[] args) {
        List<String> stringList = Arrays.asList( new String[]{"ABCDEF", "AA", "BEF", "A", "AABB"} );
        Set<String> stringSet = new HashSet<>( stringList );
        String s[] = stringSet.toArray( new String[stringSet.size()] );
        for (int i = 0; i < s.length; i++) {
            for (int j = i + 1; j < s.length; j++) {
                if (s[i].compareTo( s[j] ) > 0) {
                    String temp = s[j];
                    s[j] = s[i];
                    s[i] = temp;
                }
            }
        }
        System.out.println("LEXICOGRAPHIC ORDER: -> "+ Arrays.toString( s ) );
    }
}

def laxilogical(string):
''' Print string in Laxilogical Order'''
string.sort()
return string

For this problem, we have to first define a string which will hold all the alphabets in the order of "a" to "z", we will store all the characters in a hashmap and then we will sort the array of strings according to the order in which the string is defined and then print the result.

Implementation:

#include<bits/stdc++.h>
using namespace std;
map<char, int> h;
bool compare(string x, string y){
for(int i = 0; i < min(x.size(), y.size()); i++){
if(h[x[i]] == h[y[i]])
continue;
return h[x[i]] < h[y[i]];
}
return x.size() < y.size();
}
int main()
{
string str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
vector<string> v = { "ABCDEF", "AA", "BEF",
"A", "AABB" };
for(int i = 0; i < str.length(); i++)
h[str[i]] = i;
sort(v.begin(), v.end(), compare);

for(auto x : v)
cout<<x<<" ";

return 0;
}

Python Solutions. Two ways to solve it-
1.

string = 'ABDEKCL'
print(''.join(string))

output- ABCDEKL

2.

a = 'ABDEKCL'
arr = []
for i in a:
    arr.append(ord(i))

arr.sort()
st = ''
for i in arr:
    st += chr(i)
    
print(st)

output- ABCDEKL