# 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:

1. Create a dictionary for the given order, where the key is the letter and the value is its position in the order.
2. 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.
3. 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
Map map = 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,
Dictionary order)
{
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++)

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```

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]