Swift Leetcode Series : Verifying an Alien Dictionary
Swift approach for verifying dictionaries
If you are unable to view the story you can also read the full story on The Swift Nerd blog with the link above.
Problem description (Difficulty: Easy)
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.
Examples
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).
Constraints
1 <= words.length <= 1001 <= words[i].length <= 20order.length == 26- All characters in
words[i]andorderare English lowercase letters.
Solution
If we try to follow our intuition with an example say [“Apple”, “Banana”] then we can easily tell that those strings are lexically sorted. For lexical order, We only check until the two strings don’t match and if character precedence of the second string is higher than character at first string at same offset, then we say thats they are not lexically ordered.
The Character mapping
Why did we arrived at the solution so fast? Because we subconscious remember than in standard english alphabets ‘A’ comes before ‘B’ and hence “Apple” -> “Banana” is correct. Here in this situation, we are given a new alphabet precedence and hence we need to save it somewhere so that we can compare the strings later on. The simple solution is to iterate over the order string and create [Character:Int] dictionary representing letters and indexes. So lower the value of index, earlier it should come in order of precedence.
Comparison Logic
Now to compare if two strings are lexically ordered or not, we can create a utility function which will accept two strings and check if string1 and string2 are lexically ordered. Note that we only need to compare characters in both the string until one string ends which is minimum of both lengths = min(string1.count, string2.count). We only need to check only until we do not find the first non-matching character pair. Why? Because if two substrings have the same prefix, they will always be in correct order until the first non-matching pair (Example :- “Application” and “Apple”, since first 4 “Appl” is common it will be always ordered. So the decision would come to “i” and “e” which would be determined by the order mapping ).
We can compare the strings in the array pairwise and if at any moment we find a pair violating the condition then we return false otherwise true in the end. (No unordered strings found! Shewww!!!).
But…We missed a corner case. (Whaaat??)
Corner Case
In cases where one string is a substring of the other then the string which is a complete substring should come first.
For example, [“Apple”, “App”] where “App” is a substring of “Apple” and thus should come first lexically. So to handle that case, we can check in the utility method before returning if first string is equal or less than the second string. (position “App” < position “Apple”). In any case where two strings are substrings are first length is greater, this is a failure condition.
Code
Thank you for reading. If you liked this article and found it useful, share and spread it like wildfire!
You can find me on TheSwiftNerd | LinkedIn | Github
