Problem overview
SortByLength gets a List<string> named words and returns a new list with the words from shortest to longest. Words of the same length go in alphabetical order. A repeated word stays repeated.
For ["banana", "fig", "apple", "kiwi"] the result is ["fig", "kiwi", "apple", "banana"]. For ["sun", "a", "moon", "sun"] it is ["a", "sun", "sun", "moon"]: both copies of "sun" are kept.
Approach: sort by a key, then by a second key
Sorting by a rule is the job of LINQ's OrderBy. You give it a lambda that returns the key to sort by, here w.Length, and it puts the items in increasing key order. It does not change the original list. It gives back a new sequence.
Words with the same length are ties. ThenBy breaks ties with a second key, here the word itself, which for strings means alphabetical order. ThenBy only reorders items that tie on the first key, so the lengths stay in order.
Since OrderBy gives a lazy sequence and the method returns a List<string>, the chain ends with ToList().
Read w => w.Length as "given a word w, the key is its length". The name w is yours to choose, and the lambda is called once per word. To reverse the order, use OrderByDescending: on ["banana", "fig", "apple", "kiwi"] it gives [banana, apple, kiwi, fig]. Sorting by the word alone, OrderBy(w => w), gives [apple, banana, fig, kiwi].
Step by step
- Build
ordered:words.OrderBy(w => w.Length).ThenBy(w => w).ToList(), stored in aList<string>. - Return
ordered. Nothing was dropped, so repeated words are still there.
The solution in C#
class Solution {
public List<string> SortByLength(List<string> words) {
List<string> ordered = words.OrderBy(w => w.Length).ThenBy(w => w).ToList();
return ordered;
}
}
The lesson's tests run this with the LINQ methods available. In a file of your own you need using System.Linq; at the top.
Details that matter
- The original list is untouched. After the call,
wordsstill holds["banana", "fig", "apple", "kiwi"], andorderedholds["fig", "kiwi", "apple", "banana"].List<T>.Sort()is the in-place alternative. - The sort is stable. Items that compare equal keep their original relative order. That does not matter here, because
ThenByorders ties, and identical words look the same. ThenBy, not a secondOrderBy. EachOrderBystarts a new sort that only cares about its own key. With["b", "aa", "a", "bb"],OrderBy(w => w.Length).ThenBy(w => w)gives[a, b, aa, bb], butOrderBy(w => w.Length).OrderBy(w => w)gives[a, aa, b, bb], which is plain alphabetical order.
Alphabetical order and capital letters
The constraints give only lowercase letters, so ThenBy(w => w) is enough. With mixed case the default string comparison depends on the machine's culture settings, and it may place a next to A. If you need plain character-code order, pass a comparer: OrderBy(x => x, StringComparer.Ordinal) puts ["b", "A", "a", "B"] in the order [A, B, a, b], with every capital before every lowercase letter.
Short inputs need no special care: a one-word list comes back as it is, and an empty list gives an empty list.
Complexity
Sorting n words takes O(n log n) comparisons, and the new list needs O(n) space.
Testing
Outputs from running the solution:
| words | Result |
|---|---|
["banana", "fig", "apple", "kiwi"] | [fig, kiwi, apple, banana] |
["dog", "cat", "ant", "bee"] | [ant, bee, cat, dog] |
["sun", "a", "moon", "sun"] | [a, sun, sun, moon] |
Common mistakes
- Leaving out
ToList(). The chain gives anIOrderedEnumerable<string>, which the method's return type does not accept. - Sorting only by length. The result looks right for some inputs because the original order of tied words is kept, but the tied words are not alphabetical in general.
- Removing duplicates. Sorting never drops items. Do not reach for
Distinct()here.
