algoadvance

Leetcode 953. 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 the lowercase English 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.

Example:

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true

Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false

Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false

Constraints:

Clarifying Questions:

  1. Are the words always non-empty strings consisting of lowercase English letters?
    Yes.
  2. Is the order string always valid and contains exactly 26 unique lowercase English letters?
    Yes.

Strategy:

  1. Create a Mapping: Create a map to store the position of each character as per the given order.
  2. Word-by-Word Comparison: Traverse through each pair of adjacent words and compare them using our map.
    • Compare letters one by one.
    • If a mismatched letter is found, use the order map to determine the correct order.
    • If a word is a prefix of another word but longer (e.g., “apple” and “app”), then it’s not sorted.
  3. Return True/False: If all adjacent words are in the correct order, return true. Otherwise, return false.

Code:

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        // Create a mapping from order to indices
        unordered_map<char, int> order_map;
        for (int i = 0; i < order.length(); ++i) {
            order_map[order[i]] = i;
        }

        for (int i = 1; i < words.size(); ++i) {
            if (!compareAlien(words[i - 1], words[i], order_map)) {
                return false;
            }
        }

        return true;
    }

private:
    bool compareAlien(const string &word1, const string &word2, unordered_map<char, int> &order_map) {
        int len1 = word1.length();
        int len2 = word2.length();
        int minLen = min(len1, len2);

        for (int i = 0; i < minLen; ++i) {
            if (word1[i] != word2[i]) {
                if (order_map[word1[i]] > order_map[word2[i]]) {
                    return false;
                }
                return true;
            }
        }
        
        // If we reached here, all the characters of the shorter word matched with the longer word.
        // In this case, we need to check the length.
        return len1 <= len2;
    }
};

int main() {
    Solution sol;
    vector<string> words1 = {"hello", "leetcode"};
    string order1 = "hlabcdefgijkmnopqrstuvwxyz";
    cout << (sol.isAlienSorted(words1, order1) ? "true" : "false") << endl;

    vector<string> words2 = {"word", "world", "row"};
    string order2 = "worldabcefghijkmnpqstuvxyz";
    cout << (sol.isAlienSorted(words2, order2) ? "true" : "false") << endl;

    vector<string> words3 = {"apple", "app"};
    string order3 = "abcdefghijklmnopqrstuvwxyz";
    cout << (sol.isAlienSorted(words3, order3) ? "true" : "false") << endl;
    
    return 0;
}

Time Complexity:

This solution is efficient given the constraints, with N up to 100 and M up to 20.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI