Start learning free

LESSON 263 OF 667 · PAIRS, SORTING & BUILT-INS

Shortest Words First in C++: sort with a Custom Lambda

Practice Read the full explanation

You get a vector of words, words. Return the words sorted from shortest to longest.

Words of the same length go in alphabetical order, from A to Z.

A word can appear more than once. Every copy stays in the result.

 

Example 1:

Input: words = ["banana", "fig", "apple", "kiwi"]
Output: ["fig", "kiwi", "apple", "banana"]
Explanation: "fig" has 3 letters and "kiwi" has 4.
"apple" has 5 and "banana" has 6.

Example 2:

Input: words = ["dog", "cat", "ant", "bee"]
Output: ["ant", "bee", "cat", "dog"]
Explanation: All four words have 3 letters.
So they go from A to Z.

Example 3:

Input: words = ["sun", "a", "moon", "sun"]
Output: ["a", "sun", "sun", "moon"]
Explanation: "sun" appears twice, so it stays twice.
Both copies come after "a" and before "moon".

 

Constraints:

  • words has 1 to 100 words.
  • Each word has 1 to 20 lowercase letters.
STEP 1 OF 3
    Ctrl + Enter to check

    C++ · PAIRS, SORTING & BUILT-INS

    Shortest Words First in C++, explained

    Problem overview

    sortByLength receives a vector of words and returns it sorted from shortest to longest. Words of the same length go in alphabetical order. A word that appears twice stays in the result twice.

    For ["banana", "fig", "apple", "kiwi"] the result is ["fig", "kiwi", "apple", "banana"]. For ["dog", "cat", "ant", "bee"] all lengths are 3, so the result is alphabetical: ["ant", "bee", "cat", "dog"]. For ["sun", "a", "moon", "sun"] it is ["a", "sun", "sun", "moon"].

    Approach: tell sort how to compare two words

    sort(words.begin(), words.end()) on its own orders strings alphabetically, so "banana" would come before "fig". To sort by length, give sort a third argument: a function that takes two elements and answers one question, "should a go before b?". A lambda written in place is the usual way to do that.

    The question has two rules. First rule: if the lengths differ, the shorter word goes first. Second rule, used only when the lengths are equal: the alphabetically earlier word goes first. For two strings, a < b is true when a comes first from A to Z.

    Step by step

    1. Call sort on the whole vector, from words.begin() to words.end(), with a lambda taking two const string&, a and b.
    2. Write rule one: if a.size() != b.size(), return a.size() < b.size().
    3. Write rule two below it: return a < b.
    4. Return words. sort rearranges the vector itself, and it never drops or adds elements, so duplicates stay.

    The solution in C++

    class Solution {
public:
    vector<string> sortByLength(vector<string> &words) {
        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            if (a.size() != b.size()) {
                return a.size() < b.size();
            }
            return a < b;
        });
        return words;
    }
};

    Details that matter:

    • The lambda answers "strictly before". It returns true only when a must go before b. For equal words it returns false both ways, which is what sort requires.
    • sort changes the vector in place. The parameter is a reference, so the caller's vector is sorted too, and the function returns a copy of it.
    • The lambda has two returns of the same type, bool, which lets the compiler work out its return type.
    • The sort is not stable, but that doesn't matter here: equal words are identical strings, and different words with the same length are ordered by rule two.

    Another way to write the rules

    Two pairs compare their first values and then their second values, so the rules can also be written as one comparison of (length, word) pairs:

    sort(words.begin(), words.end(), [](const string& a, const string& b) {
    return make_pair(a.size(), a) < make_pair(b.size(), b);
});

    On ["sun", "a", "moon", "sun"] it gives a sun sun moon, the same as the lesson's code. The two-rule version spells out each step, which is what the lesson practices.

    Edge cases and common mistakes

    • Forgetting the tie rule. With only rule one, words of equal length may come out in any order, so ["dog", "cat", "ant", "bee"] is not guaranteed to give ["ant", "bee", "cat", "dog"].
    • Returning a.size() <= b.size(). A comparison must return false for equal elements. With <= it is invalid for sort and may misbehave or even crash on inputs with equal words, such as the duplicate "sun".
    • Wrong direction. a.size() > b.size() puts the longest words first.
    • Sorting alphabetically only. The plain sort would give ["apple", "banana", "fig", "kiwi"] for example 1.
    • Removing duplicates. Sorting never does; both "sun" copies remain.

    Why two rules, in this order

    The order of the rules is part of the answer. Length is the main key, so it is tested first. Alphabetical order is only a tie-breaker, so it is tested second, and only runs when the lengths are equal. Swapping the rules would sort alphabetically and use length only to break ties, which gives ["a", "moon", "sun", "sun"] for the third example instead of the expected result.

    Testing

    • ["banana", "fig", "apple", "kiwi"] gives fig kiwi apple banana.
    • ["dog", "cat", "ant", "bee"] gives ant bee cat dog.
    • ["sun", "a", "moon", "sun"] gives a sun sun moon.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free