Verifying an Alien Dictionary

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.

For example:

1. Example 1:

   Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
   Output: true
   Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.
   

2. Example 2:

   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.
   

3. Example 3:

   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.
   

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 20
• order.length == 26
• All characters in words[i] and order are English lowercase letters.

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] orderMap = new int[26];
        for (int i = 0; i < order.length(); i++) {
            orderMap[order.charAt(i) - 'a'] = i;
        }

        for (int i = 0; i < words.length - 1; i++) {
            if (!isLessThanOrEqualTo(words[i], words[i + 1], orderMap)) {
                return false;
            }
        }

        return true;
    }

    private boolean isLessThanOrEqualTo(String word1, String word2, int[] orderMap) {
        int minLength = Math.min(word1.length(), word2.length());
        for (int i = 0; i < minLength; i++) {
            char char1 = word1.charAt(i);
            char char2 = word2.charAt(i);
            if (orderMap[char1 - 'a'] < orderMap[char2 - 'a']) {
                return true;
            } else if (orderMap[char1 - 'a'] > orderMap[char2 - 'a']) {
                return false;
            }
        }
        return word1.length() <= word2.length();
    }
}

Naive Approach

The naive approach would involve comparing each pair of adjacent words in the given array and checking if they are in the correct order according to the alien alphabet. This can be done by iterating through the words and comparing the characters at each position until a difference is found or one of the words is exhausted. The time complexity for this would be O(N * M), where N is the number of words and M is the average length of the words.

Optimal Solution

The optimal solution involves creating a mapping of the alien alphabet to integer values, which can be done in O(1) time since there are only 26 letters. Then, compare each pair of adjacent words using this mapping. This comparison takes O(M) time, where M is the length of the shorter word. Iterate through the words, comparing each pair, resulting in a total time complexity of O(N * M), where N is the number of words. This is similar to the naive approach in terms of time complexity, but using a map makes the comparisons cleaner and easier to understand.

Big(O) Run-time Analysis

1. Mapping the Alien Alphabet: Creating the orderMap takes O(1) time because the order string has a fixed length of 26 (lowercase English letters).
2. Iterating through the Words: The main loop iterates through the words array, which has a length of N (number of words). Inside this loop, the isLessThanOrEqualTo function is called.
3. Comparing Words: The isLessThanOrEqualTo function compares two words, word1 and word2, up to the length of the shorter word (M). This comparison involves looking up characters in the orderMap, which takes O(1) time per character.

Therefore, the overall time complexity is O(N * M), where N is the number of words and M is the average length of the words. This is because, in the worst case, we compare each pair of adjacent words, and the comparison takes O(M) time.

Big(O) Space Usage Analysis

1. orderMap: The orderMap is an integer array of size 26, which stores the order of each character in the alien alphabet. Since the size of this array is constant, the space used is O(1).
2. Other Variables: The other variables used in the algorithm (such as loop counters and temporary variables) take up constant space, O(1).

Therefore, the overall space complexity is O(1), as the space used does not depend on the input size.

Edge Cases and Handling

1. Empty Input: If the words array is empty or contains only one word, the array is considered sorted. The algorithm should handle this gracefully by returning true in such cases.
2. Empty Words: If the words array contains empty strings, the algorithm should still function correctly, considering an empty string as lexicographically smaller than any non-empty string.
3. Different Length Words: If one word is a prefix of another (e.g., "apple" and "app"), the shorter word should come first. The algorithm handles this correctly in the isLessThanOrEqualTo function by checking the lengths of the words when all characters are equal up to the length of the shorter word.
4. Invalid Input: Although the constraints specify that all characters are lowercase English letters, it's a good practice to add validation for invalid characters in a production environment. This can be done by adding a check to ensure that each character in the words and order is a lowercase letter.