Given a custom alphabet order (a permutation of letters) and a list of words,
return true if the words are sorted in non-decreasing order according to that custom
alphabet.
detectDictionary(order, words)
Input format: order | words.
order="hlabcdefgijkmnopqrstuvwxyz", words=[hello, leetcode] // → true
order="worldabcefghijkmnpqstuvxyz", words=[word, world, row] // → false
order="abcdefghijklmnopqrstuvwxyz", words=[apple, app] // → false
This is string comparison, but under a custom letter order given as a permutation — the comparison logic needs to be parameterized by that order, not assume standard alphabetical order.
Re-scanning the order string to find each letter's position every comparison would be wasteful. Precompute once: a lookup from letter to its rank (index) in the custom order. After that, comparing two letters is an O(1) rank lookup, not a re-scan.
With ranks available, compare words the usual way, substituting rank lookups for alphabet order: walk both character by character. The first differing pair, whichever has the smaller rank, decides — nothing after that matters.
If one word runs out before any difference ("app" vs "apple"), the shared characters never differ. In standard dictionary order, the shorter prefix word comes first. So reaching the end of the shorter word without a mismatch is only correctly ordered if the first word is no longer than the second — "apple" before "app" is invalid, since "app" being a prefix means it should come first.
With one reliable "can A come before B" comparison, check every adjacent pair in the list. If any pair is out of order, the whole list fails — stop immediately. If every adjacent pair passes, the whole list is sorted, since non-decreasing order between neighbors implies it transitively across the whole sequence.
Cost is proportional to total characters across all words: the rank table build is proportional to alphabet size, and each comparison only looks as far as needed to find a difference or exhaust the shorter word. No extra structures beyond the small fixed-size rank table, so constant extra space beyond the input.
def detect_dictionary(order, words):
rank = {c: i for i, c in enumerate(order)}
def in_order(a, b):
n = min(len(a), len(b))
for i in range(n):
if a[i] != b[i]:
return rank[a[i]] < rank[b[i]]
return len(a) <= len(b)
for i in range(1, len(words)):
if not in_order(words[i - 1], words[i]):
return False
return True
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.