Loading page…
Practice problem · easy
An online store prints shelf labels for its warehouse. The warehouse does not sort labels in the usual a-to-z order. It uses its own letter order, written as a string of all 26 lowercase letters from first to last, such as qwertyuiopasdfghjklzxcvbnm, the order of a keyboard.
Your team lead asks: "Check whether a list of labels is already in warehouse order, so we can skip sorting it."
Write labels_in_shelf_order(labels, ranking).
ranking has each of the 26 lowercase letters exactly once. The earlier a letter appears in ranking, the smaller it is.true if every label is smaller than or equal to the label after it, and false otherwise.Input: labels = ["tea", "tin", "ant"], ranking = "qwertyuiopasdfghjklzxcvbnm"
Output: trueFirst write down the position of every letter in ranking. Here t is at 4, e at 2, i at 7, a at 10 and n at 24. Then compare each label with the next one.
| Pair | First different letters | Positions | In order? |
|---|---|---|---|
| tea, tin | e and i (t matches) | 2 and 7 | yes, 2 < 7 |
| tin, ant | t and a | 4 and 10 | yes, 4 < 10 |
Both neighbouring pairs are in order, so the answer is true.
Input: labels = ["ant", "tea"], ranking = "qwertyuiopasdfghjklzxcvbnm"
Output: falseThe first letters are a (position 10) and t (position 4). A label starting with a ranks after one starting with t here, so ant is out of order.
Input: labels = ["pear", "pea"], ranking = "qwertyuiopasdfghjklzxcvbnm"
Output: falsepea is the start of pear, so pea must come first.
1 ≤ len(labels) ≤ 100,000, and each label has 1 to 20 lowercase letters.ranking is a rearrangement of the letters a to z, so it has 26 letters and no repeats.There can be 100,000 labels, which gives about 5 billion pairs of labels. Checking every pair never finishes. Checking only each label against the next one costs 100,000 comparisons of at most 20 letters each.
labels_in_shelf_order · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.