外星字典算法时间复杂度咨询：我的实现复杂度是否为O(N²)？

Problem Statement #

An alien language uses lowercase English letters, but the order of the letters is some permutation of the lowercase alphabet. Given a sequence of words written in this alien language and the order of the alphabet, return true if and only if the given words are sorted lexicographically in this alien language.

My Implementation #

var isAlienSorted = function(words, order) {
 if(!words || words.length === 0) return true;
 const dict = {};
 for (let i=0; i<order.length; i++) {
 dict[order[i]] = i;
 }
 for(let i=1; i<words.length; i++) {
 if(!helper(words[i-1], words[i], dict)){
 return false;
 }
 }
 return true;
};
const helper = (str1, str2, order) => {
 for(let j=0; j<str1.length; j++) {
 if(j > str2.length-1) return false;
 if(order[str1[j]] > order[str2[j]]) return false
 else if(order[str1[j]] < order[str2[j]]) return true;
 }
 return true;
}

My Question #

I originally thought the time complexity was O(N) (where N is the number of elements in the words array), but since there's a loop inside the helper function, I'm unsure if this makes the time complexity O(N²). I'm reaching out to clarify this.

Answer #

Let's break down the time complexity of your algorithm clearly—it's actually O(L), where L is the total number of characters across all words in the words array. Here's the step-by-step reasoning:

1. Building the character priority dictionary
   You iterate through the order string, which is always a permutation of 26 lowercase letters. Since 26 is a fixed constant, this step takes O(1) time (constant time), so it doesn't affect the overall complexity.

2. Checking adjacent word pairs
   You loop through words.length - 1 pairs of adjacent words (let's call the number of words M). Each iteration calls the helper function, but the key detail is the total number of character comparisons across all helper calls:

   • The helper function stops as soon as it finds the first differing character between two words, or when it finishes traversing the shorter of the two words.
   • Globally, every character in the words array is compared at most once. Even in the worst case (all words share long identical prefixes), each character is only checked during one adjacent word comparison.

This means the total number of operations from all helper calls is bounded by the total number of characters L, not the square of the number of words.

To clarify your initial confusion: The complexity isn't O(N²) because we aren't comparing every word to every other word (which would be O(N²) operations). Instead, we only compare adjacent pairs, and each comparison's cost scales with the length of the words, not the number of words. If you want to frame it in terms of word count N and maximum word length K, it can also be written as O(NK), but this is equivalent to O(L) since L (total characters) is always ≤ NK.

内容的提问来源于stack exchange，提问作者myTest532 myTest532