Running tests and verifying code is the work order for the day. I have a Command Line Interface (CLI) for the storage server sending the equivalent of ping requests but at the application level. Since I started the test at around 09:30 AM today it has processed so far 1,190,833 requests and associated responses without a single warning or error entry in the log files. I will stop the test at the end of the work day.
Earlier today I was going to work on a different LeetCode problem, but when I did a search on “alien” two problems were selected. Since one was flagged Easy and the second Hard, I thought some items might apply from the first one to the second problem. Hopefully it would not take too long to solve the Easy problem so I could tackle the Hard after the end of the workday. Boy was I mistaken.
In this post I will refer to LeetCode 953 Verifying an Alien Dictionary, which I was not able to solve as expected. I will proceed as I always and will explain my code which has not been accepted. In addition I also copied from LeetCode two additional solutions. I tested them on LeetCode and they are both accepted.
I will attempt to solve the problem on my computer. When done I will copy and paste my code on the LeetCode site. Will then test it and hopefully submit it. The first test example out of three provided by LeetCode was rejected.
I will attempt to solve this problem using Java on a Windows 10 computer using the VSCode IDE.
In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters. Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographically in this alien language. Constraints: o 1 <= words.length <= 100 o 1 <= words[i].length <= 20 o order.length == 26 o All characters in words[i] and order are English lowercase letters.
The problem seems to be pretty straightforward. We are given a set of words and we need to check the words until we find one that is not in ascending sorted lexicographically order. In other words if we are provided two words the first should be in a lower place than the second. If we are provided three words, the first would be in the lowest order, followed by the second in a higher (or same) level, and the third word would be the highest of the set.
public boolean isAlienSorted(String[] words, String order) {
}
The signature for the method we need to implement is clear. We get a list of words in alien language followed by the alphabet indicating the order and we need to return true if the words are or false if not in sorted lexicographically order.
hello,leetcode
hlabcdefgijkmnopqrstuvwxyz
main <<< words: [hello, leetcode]
main <<< order: hlabcdefgijkmnopqrstuvwxyz
main <<< words[0].compareTo(words[1]): -4
main <<< i: 0 h,l
main <<< diff: -4
main <<< i: 1 e,e
main <<< diff: 0
main <<< i: 2 l,e
main <<< diff: 7
main <<< i: 3 l,t
main <<< diff: -8
main <<< i: 4 o,c
main <<< diff: 12
<<< hm: {a=2, b=3, c=4, d=5, e=6, f=7, g=8, h=0, i=9, j=10, k=11, l=1, m=12, n=13, o=14, p=15, q=16, r=17, s=18, t=19, u=20, v=21, w=22, x=23, y=24, z=25}
<<< ca1: [h, e, l, l, o]
<<< ca2: [l, e, e, t, c, o, d, e]
<<< j: 0 0 <= 1
<<< j: 1 6 <= 6
<<< j: 2 1 <= 6
<<< j: 3 1 <= 19
<<< j: 4 14 > 4
<<< 14 > 4
main <<< isAlienSorted: false
main <<< isAlienSorted1: true
main <<< isAlienSorted2: true
hello,leetcode
abcdefghijklmnopqrstuvwxyz
main <<< words: [hello, leetcode]
main <<< order: abcdefghijklmnopqrstuvwxyz
main <<< words[0].compareTo(words[1]): -4
main <<< i: 0 h,l
main <<< diff: -4
main <<< i: 1 e,e
main <<< diff: 0
main <<< i: 2 l,e
main <<< diff: 7
main <<< i: 3 l,t
main <<< diff: -8
main <<< i: 4 o,c
main <<< diff: 12
<<< hm: {a=0, b=1, c=2, d=3, e=4, f=5, g=6, h=7, i=8, j=9, k=10, l=11, m=12, n=13, o=14, p=15, q=16, r=17, s=18, t=19, u=20, v=21, w=22, x=23, y=24, z=25}
<<< ca1: [h, e, l, l, o]
<<< ca2: [l, e, e, t, c, o, d, e]
<<< j: 0 7 <= 11
<<< j: 1 4 <= 4
<<< j: 2 11 > 4
<<< 11 > 4
main <<< isAlienSorted: false
main <<< isAlienSorted1: true
main <<< isAlienSorted2: true
word,world,row
worldabcefghijkmnpqstuvxyz
main <<< words: [word, world, row]
main <<< order: worldabcefghijkmnpqstuvxyz
main <<< words[0].compareTo(words[1]): -8
main <<< i: 0 w,w
main <<< diff: 0
main <<< i: 1 o,o
main <<< diff: 0
main <<< i: 2 r,r
main <<< diff: 0
main <<< i: 3 d,l
main <<< diff: -8
<<< hm: {a=5, b=6, c=7, d=4, e=8, f=9, g=10, h=11, i=12, j=13, k=14, l=3, m=15, n=16, o=1, p=17, q=18, r=2, s=19, t=20, u=21, v=22, w=0, x=23, y=24, z=25}
<<< ca1: [w, o, r, d]
<<< ca2: [w, o, r, l, d]
<<< j: 0 0 <= 0
<<< j: 1 1 <= 1
<<< j: 2 2 <= 2
<<< j: 3 4 > 3
<<< 4 > 3
main <<< isAlienSorted: false
main <<< isAlienSorted1: false
main <<< isAlienSorted2: false
apple,app
abcdefghijklmnopqrstuvwxyz
main <<< words: [apple, app]
main <<< order: abcdefghijklmnopqrstuvwxyz
main <<< words[0].compareTo(words[1]): 2
main <<< i: 0 a,a
main <<< diff: 0
main <<< i: 1 p,p
main <<< diff: 0
main <<< i: 2 p,p
main <<< diff: 0
<<< hm: {a=0, b=1, c=2, d=3, e=4, f=5, g=6, h=7, i=8, j=9, k=10, l=11, m=12, n=13, o=14, p=15, q=16, r=17, s=18, t=19, u=20, v=21, w=22, x=23, y=24, z=25}
<<< ca1: [a, p, p, l, e]
<<< ca2: [a, p, p]
<<< j: 0 0 <= 0
<<< j: 1 15 <= 15
<<< j: 2 15 <= 15
main <<< isAlienSorted: false
main <<< isAlienSorted1: false
main <<< isAlienSorted2: false
We are provided with two input lines. The first is the list of words and the second the order of the letters in the alien dictionary.
Our test code seems to read the provided input and return an array of words and the dictionary.
Please disregard all output until the last three lines. It seems we have three functions that attempt to solve the problem at hand. The first is my solution. The other two are calls to methods accepted by LeetCode. There seems to be an issue with my approach.
Please note that the second test case contains the same two words, and incredibly the order of characters in the dictionary matches ours. Go figure!
Note that the last three lines flag the two words “hello” and “leetcode” as not in sorted lexicographically order.
The other two test cases seem to match in all three implementations.
/**
* Test scaffolding.
*
* !!! NOT PART OF THE SOLUTION !!!
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read alien words ****
String[] words = br.readLine().trim().split(",");
// **** read dictionary ****
String order = br.readLine().trim();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< words: " + Arrays.toString(words));
System.out.println("main <<< order: " + order);
System.out.println("main <<< words[0].compareTo(words[1]): " + words[0].compareTo(words[1]));
for (int i = 0; i < Math.min(words[0].length(), words[1].length()); i++) {
// ???? ????
int v1 = words[0].charAt(i);
int v2 = words[1].charAt(i);
int diff = v1 - v2;
// ???? ????
System.out.println("main <<< i: " + i + " " + words[0].charAt(i) + "," + words[1].charAt(i));
System.out.println("main <<< diff: " + diff);
}
// **** check and display result ****
System.out.println("main <<< isAlienSorted: " + isAlienSorted(words, order));
// **** check and display result ****
System.out.println("main <<< isAlienSorted1: " + isAlienSorted1(words, order));
// **** check and display result ****
System.out.println("main <<< isAlienSorted2: " + isAlienSorted2(words, order));
}
As we assumed earlier, our test code reads the two input lines. The set of words are placed in an array and the dictionary in a string.
Let’s skip to the last three statements. They make calls to three different methods and the results are displayed.
At this point let’s take a look at the code labeled with “????” strings.
We display the list of words which in the first two test cases are “hello” and “leetcode”. We then display the dictionary.
The next line displays the results of comparing the two words. Note that we get as a result -4 on both test cases. Since the Java language understands English but not alien, it compares the two words character by character checking for the same value until the length of the shortest string. The first two letters to be compared are ‘h’ and ‘l’ which in English (actually ASCII) map to 104 and 108 respectively. Note than 104 -108 = -4 which happens to be the value returned by the String.compareTo() method. Since the first two characters DO NOT MATCH, the method returns -4.
We then enter a loop in which we will traverse the first two (and only two) strings character by character until we reach the length of the shortest word.
For each character we extract the value (in ASCII) and compute the difference. We then display the location of the characters in the respective strings, and the associated characters followed on a second line by the difference between the values.
Once again, note that the comparisons are not based on the alien alphabet but on the ASCII values using our English alphabet.
Let’s now concentrate only on the values of diff. The values are the difference of the corresponding characters in the string. If diff is negative or zero, it indicates that the first string is lexicographically in a lower level than the second because ‘h’ < ‘l’, ‘e’ == ‘e’, and ‘l’ > ‘e’. This implies that these two words are NOT in lexicographical order using the ASCII character set.
/**
* Return true if and only if the given words
* are sorted lexicographicaly in this alien language.
*
* !!!! My solution rejected by LeetCode !!!!
*/
static boolean isAlienSorted(String[] words, String order) {
// **** sanity checks ****
if (words.length < 2)
return true;
// **** initialization ****
char[] chars = order.toCharArray();
HashMap<Character, Integer> hm = new HashMap<>();
for (int i = 0; i < chars.length; i++) {
hm.put(chars[i], i);
// hm.put(chars[i], 97 + i);
}
// ???? ????
System.out.println("<<< hm: " + hm.toString());
// **** traverse array of words comparing adjacent words ~O(2m)****
for (int i = 0; i < words.length - 1; i++) {
// **** for ease of use ****
char[] ca1 = words[i].toCharArray();
char[] ca2 = words[i + 1].toCharArray();
// ???? ????
System.out.println("<<< ca1: " + Arrays.toString(ca1));
System.out.println("<<< ca2: " + Arrays.toString(ca2));
// **** compare adjacent words ~O(n)****
for (int j = 0; j < Math.min(ca1.length, ca2.length); j++) {
// ???? ????
if (hm.get(ca1[j]) <= hm.get(ca2[j]))
System.out.println("<<< j: " + j + " " + hm.get(ca1[j]) + " <= " + hm.get(ca2[j]));
else
System.out.println("<<< j: " + j + " " + hm.get(ca1[j]) + " > " + hm.get(ca2[j]));
// **** compare characters ****
if (hm.get(ca1[j]) > hm.get(ca2[j])) {
// ???? ????
System.out.println("<<< " + hm.get(ca1[j]) + " > " + hm.get(ca2[j]));
// **** ****
return false;
}
}
// **** compare word length ****
if (ca1.length > ca2.length)
return false;
}
// **** words are in scending order ****
return true;
}
We start by performing a sanity check. We then initialize a hash map with the characters of the alien dictionary associating each with their order. The first character gets a 0, the second character a 1, and so forth. The hash map is then displayed.
In the first example we can see that ‘h’ is assigned 0, ‘l’ is assigned 1, ‘a’ is assigned 2, and so forth. This is identical to what we so in English with the only difference that ASCII ‘a’ has an assigned value of 97. By assigning an offset of 97 to all lowercase characters the difference between characters is not changed.
We now enter a loop in which we will compare two consecutive strings. The idea is that if we find a string that is out of order we will return a false. If all strings match we should return true with a consideration which we will discuss shortly.
We extract the characters from the two strings in question into two character arrays. The strings are then displayed so we can follow the process.
Now we enter a loop to check corresponding characters. Since the strings need to be in lexicographical order if the first string has a character with a larger value than the second one, we should return false. Note that we cannot exit after the first or second, or third character. We need to check all associated characters. We will take care of strings with different lengths shortly after.
In our second test case we see that ‘hello’ and ‘leetcode’ maintain the expected association for the letters ‘hell’ (smaller values) and ‘leet’ (same or larger values). When we reach the fifth set of characters, we compare ‘o’ with ‘c’. This time, ‘o’ is larger than ‘c’ so we return false. This is with ASCII values.
Back to our first example, we compare ‘hell’ and ‘leet’ and the alien character set cooperates as illustrated. But when we reach the fifth set of characters we have ‘o’ with a value of 14 and ‘c’ with a value of 4. Since 14 > 4 we need to return false.
That is my case. I must be missing something in my interpretation of the problem because my solution returns false while LeetCode expects true.
/**
* Return true if and only if the given words
* are sorted lexicographicaly in this alien language.
*
* Solution accepted by LeetCode.
*/
static boolean isAlienSorted1(String[] words, String order) {
// **** ****
int[] index = new int[26];
for (int i = 0; i < order.length(); ++i)
index[order.charAt(i) - 'a'] = i;
// ???? ????
// System.out.println("<<< index: " + Arrays.toString(index));
// **** ****
search: for (int i = 0; i < words.length - 1; ++i) {
String word1 = words[i];
String word2 = words[i+1];
// ???? ????
// System.out.println("<<< word1: " + word1);
// System.out.println("<<< word2: " + word2);
// Find the first difference word1[k] != word2[k].
for (int k = 0; k < Math.min(word1.length(), word2.length()); ++k) {
// ???? ????
// System.out.println("<<< " + word1.charAt(k) + " != " + word2.charAt(k));
// **** ****
if (word1.charAt(k) != word2.charAt(k)) {
// ???? ????
// System.out.println("<<< " + index[word1.charAt(k) - 'a'] + " > " +
// index[word2.charAt(k) - 'a']);
// If they compare badly, it's not sorted.
if (index[word1.charAt(k) - 'a'] > index[word2.charAt(k) - 'a'])
return false;
continue search;
}
}
// **** if we didn't find a first difference, the words are like ("app", "apple") ****
if (word1.length() > word2.length())
return false;
}
// **** words in ascending order ****
return true;
}
I copied this solution from the LeetCode web site. This implementation returns true on the first two test cases.
/**
* Return true if and only if the given words
* are sorted lexicographicaly in this alien language.
*
* Solution accepted by LeetCode.
*/
static boolean isAlienSorted2(String[] words, String order) {
// **** ****
if (words == null || words.length == 0 || order == null || order.length() == 0)
return false;
// **** ****
Comparator<String> comparator = new Comparator<String>(){
@Override
public int compare(String str1, String str2) {
for (int i = 0; i < Math.min(str1.length(), str2.length()); i++) {
char a = str1.charAt(i), b = str2.charAt(i);
if (a != b) {
if (order.indexOf(a) > order.indexOf(b)) return 1;
else return -1;
}
}
if (str1.length() > str2.length()) return 1;
else if (str1.length() == str2.length()) return 0;
else return -1;
}
};
PriorityQueue<String> pq = new PriorityQueue<>(words.length, comparator);
for (String s: words) pq.offer(s);
int index = 0;
// **** ****
while (!pq.isEmpty()) {
if (!pq.poll().equals(words[index++]))
return false;
}
return true;
}
I also copied this solution from LeetCode. This implementation also returns true on the first two cases.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 6,134 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com