Verifying an Alien Dictionary

class Solution {
    public boolean isOrderedAccordingToAlienDictionary(String[] arr, String dictOrder) {
        int[] dictMap = new int[26];
        for (int index = 0; index < dictOrder.length(); index++){
            dictMap[dictOrder.charAt(index) - 'a'] = index;
        }
    
        for (int wordIndex = 0; wordIndex < arr.length - 1; wordIndex++) {
    
            for (int charIndex = 0; charIndex < arr[wordIndex].length(); charIndex++) {
                if (charIndex >= arr[wordIndex + 1].length()) return false;
    
                if (arr[wordIndex].charAt(charIndex) != arr[wordIndex + 1].charAt(charIndex)) {
                    int firstCharIndex = arr[wordIndex].charAt(charIndex) - 'a';
                    int secondCharIndex = arr[wordIndex + 1].charAt(charIndex) - 'a';
                    if (dictMap[firstCharIndex] > dictMap[secondCharIndex]) return false;
                    else break;
                }
            }
        }
    
        return true;
    }
}

The provided Java code defines a class Solution containing a method isOrderedAccordingToAlienDictionary, which checks if a given array of strings (arr) is sorted according to the rules of a new dictionary order specified by the string dictOrder. Here's a breakdown of how the solution operates:

• Initialization of Mapping:

  • Creates an integer array dictMap to map each character to its priority in the alien dictionary. The size of this array is 26, assuming only lower case English letters are used.
  • Iterates through each character in dictOrder. For each character, the index is stored in the dictMap at the position corresponding to the character's difference from 'a'. This setup provides an easy way to compare the order of any two characters according to the alien dictionary.

• Verification of Order:

  • Iterates through each word in the array arr except the last one, comparing it with the next word to ensure they are in the correct order.
  • For each pair of words, compares characters one by one. If character lengths are exceeded (the first word is longer than the corresponding second word), it returns false immediately, indicating that the order is violated.
  • When two characters differ, their indices (from dictMap) are retrieved and compared. If the character from the first word has a higher index than that in the second word, it returns false indicating incorrect order.
  • If a character from the first word has a lower index than the corresponding character in the second word (meaning it is correctly ordered), the inner loop breaks and comparison moves to the next pair of words.

• Final Output:

  • Returns true if no violations in the order are found, indicating the words are sorted according to the alien dictionary.

Ensure to handle the following edge cases:

• Empty arr or dictOrder.
• arr containing a single word.
• dictOrder containing non-unique characters.

This function encapsulates both the initialization of the dictionary mapping and the verification of the array order in a streamlined manner utilizing minimal space for dictionary mapping.

class Solution:
    def isOrdered(self, word_list: List[str], alien_order: str) -> bool:
        char_position = {}
        for idx, character in enumerate(alien_order):
            char_position[character] = idx
    
        for word_idx in range(len(word_list) - 1):
            for char_idx in range(len(word_list[word_idx])):
                if char_idx >= len(word_list[word_idx + 1]): return False
                if word_list[word_idx][char_idx] != word_list[word_idx + 1][char_idx]:
                    if char_position[word_list[word_idx][char_idx]] > char_position[word_list[word_idx + 1][char_idx]]: 
                        return False
                    break
    
        return True

In the provided Python code, the goal is to verify if a list of words follows a specific lexicographical order based on an alien language alphabet. The solution involves checking if words in the list adhere to an order specified by the character sequence in alien_order.

The main steps performed in the code are:

1. Map each character in the alien alphabet to its position using a dictionary char_position. This allows for fast comparison between characters by their index positions.
2. Compare adjacent words in the word_list to ensure they are in the correct order. The comparison is performed character by character:
   • If the current character of the first word has a higher index than the same position character in the next word according to char_position, the word list is out of order, and the function returns False.
   • If the compared characters are the same, the comparison continues to the next character.
   • If all characters in the shorter word match the beginning of the longer word and no earlier mismatch is found, the loop breaks to the next pair of words, continuing the sequence check.
3. The function returns True if all word pairs meet the criteria of the alien dictionary order. If any comparison fails, it immediately returns False.

The solution efficiently processes each pair of words only until the first out-of-order character is found or until the end of the shorter word is reached, ensuring optimal performance with respect to the input size.