Problem overview
sortByLength receives a list of words and returns them sorted from shortest to longest. Words with the same length go in alphabetical order. A repeated word appears as many times as it was given.
For ["banana", "fig", "apple", "kiwi"] the result is fig, kiwi, apple, banana (lengths 3, 4, 5, 6). For ["dog", "cat", "ant", "bee"] every word has 3 letters, so the length decides nothing and the alphabet gives ant, bee, cat, dog. For ["sun", "a", "moon", "sun"] the result is a, sun, sun, moon: both copies of "sun" stay.
Approach
This is a sort with two keys. The first key is the length. The second key, used only when two words tie on the first, is the word itself, which strings compare alphabetically.
Kotlin's sortedWith takes a comparator, and compareBy builds one from lambdas. Each lambda turns an item into a value to compare, and compareBy tries them in order. Inside a lambda with one parameter, it is the current item.
Step by step
- Call
words.sortedWith(...)withcompareBy({ it.length }, { it }). The first lambda gives the length, the second gives the word. The result goes inordered. - Return
ordered.
sortedWith returns a new list. The list you passed in is not changed, and no word is dropped or added, so duplicates survive.
The solution in Kotlin
class Solution {
fun sortByLength(words: List<String>): List<String> {
val ordered = words.sortedWith(compareBy({ it.length }, { it }))
return ordered
}
}
On the three examples it returns:
[fig, kiwi, apple, banana]
[ant, bee, cat, dog]
[a, sun, sun, moon]
(The brackets and commas are how Kotlin prints a list.)
Another way to write the comparator
The same ordering can be spelled out as a chain, which some people find easier to read:
val ordered = words.sortedWith(compareBy<String> { it.length }.thenBy { it })
It gives the same result, [fig, kiwi, apple, banana], for the first example. The original words is still [banana, fig, apple, kiwi] afterwards, because sorting made a new list.
Why both keys are needed
With only the length, words.sortedBy { it.length } gives the right lengths but doesn't promise alphabetical order among equal lengths. That function keeps tied words in their original order, so ["dog", "cat", "ant", "bee"] comes back as [dog, cat, ant, bee]. The second lambda { it } is what puts them from A to Z.
Plain sorted() goes the other way: it sorts alphabetically only, so ["sun", "a", "moon", "sun"] becomes a, moon, sun, sun, with "moon" before "sun" although it is longer.
Testing
A list with several ties is a good check. For ["pear", "fig", "kiwi", "date", "plum"] the result is [fig, date, kiwi, pear, plum]: "fig" first because it is the only 3-letter word, then the four 4-letter words from A to Z. Swapping the lambdas on the same input gives [date, fig, kiwi, pear, plum], which is plain alphabetical order.
Sorting a list of n words takes about n log n comparisons, and each comparison looks at no more than 20 letters.
Edge cases and common mistakes
- Swapping the lambdas.
compareBy({ it }, { it.length })sorts alphabetically first, and length would only be consulted for identical words, which are the same length anyway. - Using a set. Converting to a set removes the repeated words.
- Uppercase letters. Here every word is lowercase. Strings compare by character code, so capitals would sort before all lowercase letters.
- One word is returned as it is.
