Solution For Verifying An Alien Dictionary
Problem Statement:
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 lexicographicaly in this alien language.
Example 1:
Input: words = [“hello”,”leetcode”], order = “hlabcdefgijkmnopqrstuvwxyz”
Output: true
Explanation: As ‘h’ comes before ‘l’ in the given order. “hello” precedes “leetcode” in lexicographically order.
Example 2:
Input: words = [“word”,”world”,”row”], order = “worldabcefghijkmnpqstuvxyz”
Output: false
Explanation: As the order of ‘d’ and ‘l’ is not defined in the given order. So “word” and “world” cannot be compared.
Example 3:
Input: words = [“apple”,”app”], order = “abcdefghijklmnopqrstuvwxyz”
Output: false
Explanation: The first three characters “app” match but the string “apple” is bigger than “app” because ‘l’ comes after ‘e’ in the given order.
Approach:
We can take the given order and create a dictionary that stores the position of each letter in the order. Then, we can compare each word in the given list with its next word. If at any point we find that the current word is greater than the next word, we can return False, as it violates the lexicographical order.
Steps:
- Create a dictionary for the given order, where the key is the letter and the value is its position in the order.
- Compare each word in the given list with its next word to check if they are sorted lexicographically using the dictionary created in step 1.
- If we find that the current word is greater than the next word, return False. If we can loop through the entire list, it means they are sorted lexicographically, so return True.
Code:
The following code implements the above approach for the given problem.
class Solution:
def isAlienSorted(self, words: List[str], order: str) -> bool:
order_map = {}
for i, c in enumerate(order):
order_map[c] = i
for i in range(len(words)-1):
word1 = words[i]
word2 = words[i+1]
for j in range(min(len(word1), len(word2))):
if word1[j] != word2[j]:
if order_map[word1[j]] > order_map[word2[j]]:
return False
break
else:
if len(word1) > len(word2):
return False
return True
Time Complexity: O(NK), where N is the number of words in the given list and K is the average length of each word in the list.
Space Complexity: O(26) = O(1), as we are using a fixed size dictionary for the given order.
Step by Step Implementation For Verifying An Alien Dictionary
public boolean isAlienSorted(String[] words, String order) { // This map will store the order of characters in the passed order string Mapmap = new HashMap<>(); for(int i = 0; i < order.length(); i++) { map.put(order.charAt(i), i); } // We will compare each word with the next word and see if they are in order for(int i = 0; i < words.length - 1; i++) { String word1 = words[i]; String word2 = words[i+1]; // If word2 is shorter than word1, then it can never be in the correct order if(word2.length() < word1.length()) { return false; } // Loop through each character in the words and compare them for(int j = 0; j < word1.length(); j++) { char char1 = word1.charAt(j); char char2 = word2.charAt(j); // If the characters are not equal, we compare their order if(char1 != char2) { if(map.get(char1) > map.get(char2)) { return false; } break; } // If we reach the end of word1 and it is shorter than word2, // then word2 is automatically in the correct order if(j == word1.length() - 1 && word1.length() < word2.length()) { break; } } } return true; }
def isAlienSorted(self, words, order): """ :type words: List[str] :type order: str :rtype: bool """ # Create a mapping of characters to integers char_to_int = {c: i for i, c in enumerate(order)} # Iterate through each word and compare it to the next word for i in range(len(words) - 1): word1 = words[i] word2 = words[i+1] # Find the first point of difference between the two words for j in range(min(len(word1), len(word2))): # If the characters are in different positions in the order, # then we know the words are not sorted if char_to_int[word1[j]] > char_to_int[word2[j]]: return False # If the characters are in the same position in the order, # we move on to the next character elif char_to_int[word1[j]] < char_to_int[word2[j]]: break # If one word is a prefix of the other, the shorter word must come first # For example, "app" is a prefix of "apple", so it should come before if len(word1) > len(word2) and word1.startswith(word2): return False # If we've gotten through all the words without returning False, # then they must all be sorted return True
/** * @param {string[]} words * @param {string} order * @return {boolean} */ var isAlienSorted = function(words, order) { };
class Solution { public: bool isAlienSorted(vector& words, string order) { // Create a mapping of characters to integers unordered_map mapping; for (int i = 0; i < order.size(); i++) { mapping[order[i]] = i; } // Compare each pair of words for (int i = 0; i < words.size() - 1; i++) { string word1 = words[i]; string word2 = words[i + 1]; // Find the first difference between the words int j; for (j = 0; j < min(word1.size(), word2.size()); j++) { if (word1[j] != word2[j]) { break; } } // If the first difference comes before the end of either word, // compare the characters at that index if (j < word1.size() && j < word2.size()) { if (mapping[word1[j]] > mapping[word2[j]]) { return false; } } // If one word is a prefix of the other, the shorter word must come first else if (word1.size() > word2.size()) { return false; } } return true; } };
using System; using System.Collections.Generic; public class GFG { // function to check if two given words are in order static bool isOrder(string a, string b, Dictionaryorder) { int min = Math.Min(a.Length, b.Length); // iterate over the min length for (int i = 0; i < min; i++) { // if a character of first string is // smaller than the corresponding // character of the second string if (order[a[i]] < order[b[i]]) return true; // if a character of first string is // greater than the corresponding // character of the second string if (order[a[i]] > order[b[i]]) return false; } // if all characters of both the strings // have been checked and both have same value return a.Length <= b.Length; } // function to check if given array of words // can be chained to form a circle static bool canFormCircle(string[] words, int n) { // create an empty dictionary Dictionary order = new Dictionary (); // one by one process all characters of // all words for (int i = 0; i < 26; i++) order.Add((char)('a' + i), 0); for (int i = 0; i < n; i++) { // iterate over the characters of // the current word for (int j = 0; j < words[i].Length; j++) { // if character's order is not // initialized if (order[words[i][j]] == 0) order[words[i][j]] = i + 1; } } // check for all words for (int i = 1; i < n; i++) { // if current word doesn't come // after the previous word as // per alien dictionary if (!isOrder(words[i - 1], words[i], order)) return false; } // we reach here means all words // are in order as per the // alien dictionary return true; } // Driver Code public static void Main() { string[] words = { "baa", "abcd", "abca", "cab", "cad" }; int n = words.Length; if (canFormCircle(words, n)) Console.WriteLine("Given words can be chained"); else Console.WriteLine("Given words can't be chained"); } } // This code is contributed by 29AjayKumar