January 21, 2011
Lexicographic Order in Java
Lexicographic Order Problem
Write java method to compare two strings lexicographically. The method should return 0 if the two strings
are Lexicographically equal. It should return 1 if the first string comes before the second string in the dictionary. It should return -1 if the first string comes after the second string in the dictionary. If the two strings share the same prefix then it should return 1 if the first string is shorter than the second string otherwise it should return 1. Here are few examples
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
Str1 = "A" Str2 = "A" Str1 is the same as Str2 then return 0 Str1 = "A" Str2 = "CBA" Str1 comes first then return 1 Str1 = "CBA" Str2 = "B" Str1 comes after then return -1 Str1 = "ABC" Str2 = "ABCD" Str1 and Str2 share a prefix but Str1 is shorter then return 1 Str1 = "ABCD" Str2 = "ABC" Str1 and Str2 share a prefix but Str2 is shorter then return -1 |
Solution
This is straight forward problem. All you need is character by character comparison but you need to keep track which string is the shorter one in order not to exceed the array limits.
Code
Here is the Java code to do that
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
//Main class public class Lexo { //Main function public static void main(String[] args) { //Input Strings String Str1 = "ABCD"; String Str2 = "ABC"; //Call function int out = LexoCompare(Str1.toCharArray(), Str2.toCharArray()); //Print output System.out.println(out); } //Comparison static int LexoCompare(char[] Str1, char[] Str2) { //Get length int ln1 = Str1.length; int ln2 = Str2.length; if (ln1 <= ln2) { max = ln1; } else { max = ln2; } //Compare characters for (int i = 0; i < max; i++) { //Str1 comes first if (Str1[i] < Str2[i]) { return 1; } //Str1 comes after else if (Str1[i] > Str2[i]) { return -1; } else { //Nothing just continue } } //If we reached this point without //a return this means the strings //share a prefix //Strings are the same length //and they are equivalent if (ln1 == ln2) { return 0; } //Str1 is shorter else if(ln1 < ln2) { return 1; } //Str2 is shorter else { return -1; } } } |