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++) 
        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