Problem overview
sortByLength gets an ArrayBuffer[String] called words and returns the words from shortest to longest. Words of the same length go in alphabetical order, and a word that appears twice stays twice. The words are lowercase letters, 1 to 20 letters each, and there are up to 100 of them.
["banana", "fig", "apple", "kiwi"]gives["fig", "kiwi", "apple", "banana"].["dog", "cat", "ant", "bee"]gives["ant", "bee", "cat", "dog"], because all four words have 3 letters.["sun", "a", "moon", "sun"]gives["a", "sun", "sun", "moon"].
Approach
The method sortBy takes a function that turns each item into a sort key, and it puts the items in the order of their keys. For a single key, such as w.length, the words sort by length. But then two words of the same length stay in whatever order they were in before, which is not alphabetical.
The fix is a key with two parts. A tuple such as (w.length, w) is compared one position at a time: first the lengths, and only when they are equal, the words themselves. Strings compare alphabetically, so equal lengths end up from A to Z. Scala knows how to order tuples of ints and strings, so no extra code is needed.
The keys for the first example
Here is the key sortBy builds for each word in ["banana", "fig", "apple", "kiwi"]:
banana -> (6,banana)
fig -> (3,fig)
apple -> (5,apple)
kiwi -> (4,kiwi)
The first numbers are all different, so the lengths alone decide the order: 3, 4, 5, 6. The second part of the key only matters when two words have the same length, as in the second example, where all four words have 3 letters.
Step by step
- Call
sortByonwordswith a function from a wordwto the tuple(w.length, w), and keep the result inordered. - Return
ordered.
Sorting rearranges words and never drops them, so duplicates stay in the result.
The solution in Scala
class Solution {
def sortByLength(words: ArrayBuffer[String]): ArrayBuffer[String] = {
val ordered = words.sortBy(w => (w.length, w))
return ordered
}
}
A few details:
w => (w.length, w)reads as: takew, give back the pair of its length and itself.sortByreturns a newArrayBufferand leaveswordsas it was. With["banana", "fig", "apple", "kiwi"],wordsstill prints asArrayBuffer(banana, fig, apple, kiwi)after the call, andorderedprints asArrayBuffer(fig, kiwi, apple, banana).- The sort is stable: items with equal keys keep their relative order. Here equal keys mean equal words, so it doesn't matter.
Another way
Because sortBy is stable, you can sort in two passes: first alphabetically, then by length. words.sorted.sortBy(w => w.length) gives ArrayBuffer(a, sun, sun, moon) for the third example. The second sort keeps the alphabetical order inside each length. The single tuple key does the same job in one step, and the order of the two parts, length first, matches the order you say it in: shortest first, then A to Z.
Testing
["banana", "fig", "apple", "kiwi"] ArrayBuffer(fig, kiwi, apple, banana)
["dog", "cat", "ant", "bee"] ArrayBuffer(ant, bee, cat, dog)
["sun", "a", "moon", "sun"] ArrayBuffer(a, sun, sun, moon)
The tests compare the words in order; Scala prints a buffer as ArrayBuffer(...) with the words separated by commas.
Common mistakes
- Sorting by length alone.
words.sortBy(w => w.length)keeps equal-length words in their original order. For["bb", "a", "cc", "aa"]it givesArrayBuffer(a, bb, cc, aa), but the right answer isArrayBuffer(a, aa, bb, cc), which(w.length, w)produces. - Swapping the tuple.
(w, w.length)sorts alphabetically first, and the length only breaks ties between identical words. - Removing duplicates. Don't convert to a set. Every copy stays.
