Verifying an Alien Dictionary

XXX.Verify Alien Dictionary

String

Sorting

Problem Statement:

Given an array of words and a custom alien language order, determine if the words are sorted lexicographically according to the alien dictionary. Each word consists of lowercase letters, and the order string contains all 26 letters of the alien alphabet.

Algorithm:

1. Create a rank array to store the index of each character in the alien order for quick comparison.
2. Compare adjacent words to verify if the first word is lexicographically smaller than the second.
3. For each pair of words:
   • Iterate through characters of both words until their first mismatch.
   • If the mismatch exists, check if the first word has a greater rank. If true, return false.
   • If no mismatch is found, ensure the first word isn't longer than the second.
4. If all words are sorted according to the alien order, return true.

Complexity:

Time: O(n × m), where n is the number of words and m is the average word length | Space: O(1).

Java Implementation:

public class Solution {

    // Array to store rank of each character in the alien order
    private final int[] rank = new int[26];

    public boolean isAlienSorted(String[] words, String order) {
        // Populate rank array
        for (int i = 0; i < order.length(); i++)
            rank[order.charAt(i) - 'a'] = i;
        
        // Compare each word with its next word
        for (int i = 1; i < words.length; i++)
            if (bigger(words[i - 1], words[i]))
                return false;
        
        return true;
    }

    // Helper function to compare two words
    boolean bigger(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        for (int i = 0; i < n && i < m; i++) {
            if (s1.charAt(i) != s2.charAt(i))
                return rank[s1.charAt(i) - 'a'] > rank[s2.charAt(i) - 'a'];
        }
        // If all characters are equal, check word lengths
        return n > m;
    }
}
                

Python Implementation:

def isAlienSorted(words, order):
    # Create a rank dictionary for character positions
    rank = {char: idx for idx, char in enumerate(order)}
    
    def bigger(w1, w2):
        for c1, c2 in zip(w1, w2):
            if c1 != c2:
                return rank[c1] > rank[c2]
        return len(w1) > len(w2)
    
    # Compare adjacent words
    for i in range(1, len(words)):
        if bigger(words[i - 1], words[i]):
            return False
    return True
                

C++ Implementation:

class Solution {
public:
    bool isAlienSorted(vector& words, string order) {
        // Create a rank array
        vector rank(26);
        for (int i = 0; i < order.size(); i++)
            rank[order[i] - 'a'] = i;

        // Compare adjacent words
        for (int i = 1; i < words.size(); i++)
            if (bigger(words[i - 1], words[i], rank))
                return false;
        
        return true;
    }

private:
    // Helper function to compare two words
    bool bigger(const string& s1, const string& s2, vector& rank) {
        int n = s1.size(), m = s2.size();
        for (int i = 0; i < min(n, m); i++) {
            if (s1[i] != s2[i])
                return rank[s1[i] - 'a'] > rank[s2[i] - 'a'];
        }
        return n > m;
    }
};