Sort Words by a Custom Alphabet

A language uses the same 26 lowercase letters as English but in a different order. alphabet is a string of length 26 listing the letters from smallest to largest.

Sort words lexicographically according to that alphabet and return the sorted list. Comparison is letter by letter; if one word is a prefix of the other, the shorter word comes first. Identical words keep their original relative order.

Examples

Input:  words = ["word", "world", "row"], alphabet = "worldabcefghijkmnpqstuvxyz"
Output: ["world", "word", "row"]
Explanation: 'l' precedes 'd' in this alphabet, so "world" < "word"; 'r' is larger than 'w'.

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

Constraints

• 0 <= len(words) <= 5 * 10**4, 1 <= len(words[i]) <= 20, lowercase letters only
• alphabet is a permutation of "abcdefghijklmnopqrstuvwxyz"
• Target complexity: O(L log n) where L is the total number of letters.

Goals

• Translate letters into ranks using a lookup table
• Sort strings by a tuple of ranks so prefixes come first
• Keep equal words in their original order