Replace words with the shortest root

Why this matters

Search engines and text tools often need to treat running, runs and run as one idea. One common method is to cut each word down to a short base form, called a root or stem. A root is a short string that other words start with. If the dictionary holds run, then running and runs both start with run, so they can be replaced by run.

This lesson solves a simple version of that task. You get a list of roots and a sentence. For each word in the sentence, replace it with the shortest root that is a prefix of the word. If no root is a prefix, keep the word as it is. The answer for cattle with the roots cat and catt is cat, because cat is shorter and is also a prefix of cattle.

The trie from the first lesson of this module is a good fit. Each root is a word stored in the trie. To find the shortest root for one word, you walk down the trie along the word's letters and stop at the first node whose end flag is set. That first flag is the shortest root, so the walk never needs to go further.

This lesson uses the trie with exact words only. It does not use wildcards, which were covered in the previous lesson, and it does not use suffix or radix structures, which appear later in the module.

Start with the rule, by hand

Take the roots cat, bat and rat, and the sentence the cattle was rattled by the battery. Work through each word.

The word cattle starts with cat, so it becomes cat. The word battery starts with bat, so it becomes bat. Words such as the and was have no root that starts them, so they stay the same.

Now the rule for the shortest root. Suppose the roots include both ca and cat, and the word is catalog. Both roots are prefixes of catalog. The shorter one, ca, is the answer, because the rule says to pick the shortest root. A trie finds it without comparing every root. It walks c, then a. At a the end flag is set, so the walk stops and returns ca.

The idea: stop at the first flag

A simple method compares each word with each root. That costs about the number of roots times the length of the word, for every word in the sentence. A trie does the same job in one walk per word.

Use the analogy of a filing cabinet, as in the first lesson of this module. The drawers are labelled by letter. Some folders are marked "a root ends here". To find the shortest root for a word, open drawers in order, one letter at a time. As soon as you find a folder marked "root ends here", you have the answer, and you do not need to look at the deeper folders. If the drawers run out before you find a mark, or the word runs out, no root applies.

This is why the walk stops early. The node for ca may have a child t for the root cat, but once the walk reaches ca and sees its flag, the search for the shortest root is over.

Trace one word step by step

Take the roots ca and cat, and the word catalog. Before reading any code, follow the walk on paper. Keep a finger on the current node and move it one letter at a time.

1. Start at the root of the trie. It stands for the empty string, and it has no end flag, so nothing is returned yet.
2. Read the first letter, c. The root has a child for c. Move the finger to that child. Its end flag is not set, because c alone is not a stored root.
3. Read the second letter, a. The c node has a child for a. Move to it. Now the finger stands on the node for ca. Its end flag is set, because ca is a stored root.
4. The flag is set, so the answer is ca. The walk does not read the rest of the word, talog, and it does not look at the t child that leads to cat.

The same walk for cattle would stop at the same place. For cab it would stop at the same place too, because cab also starts with ca. The word dog would stop at step 2, because the root has no child for d and the finger has nowhere to go. The walk then returns dog unchanged.

Notice what the walk does not do. It does not compare catalog with ca and then with cat as two separate string checks. The trie already holds both roots in one shared path. The c and a steps are shared, and the decision happens at the first flag.

The first worked example

Here is the full program. The trie stores the roots. The function shortestRoot walks the trie for one word. The function replaceWords builds the trie, splits the sentence into words, and joins the results back together with single spaces.

#include <array>
#include <cstddef>
#include <iostream>
#include <memory>
#include <sstream>
#include <stdexcept>
#include <string>
#include <string_view>
#include <vector>
 
struct Node {
    std::array<std::unique_ptr<Node>, 26> children{};
    bool isEnd = false;
};
 
class RootTrie {
public:
    void addRoot(std::string_view root) {
        Node* current = &root_;
        for (char ch : root) {
            const std::size_t index = letterIndex(ch);
            if (!current->children[index]) {
                current->children[index] = std::make_unique<Node>();
            }
            current = current->children[index].get();
        }
        current->isEnd = true;
    }
 
    // Returns the shortest stored root that is a prefix of word, or word itself.
    std::string shortestRoot(std::string_view word) const {
        const Node* current = &root_;
        for (std::size_t i = 0; i < word.size(); ++i) {
            current = current->children[letterIndex(word[i])].get();
            if (current == nullptr) {
                break;
            }
            if (current->isEnd) {
                return std::string(word.substr(0, i + 1));
            }
        }
        return std::string(word);
    }
 
private:
    Node root_;
 
    static std::size_t letterIndex(char ch) {
        if (ch < 'a' || ch > 'z') {
            throw std::invalid_argument(std::string("not a lowercase letter: ") + ch);
        }
        return static_cast<std::size_t>(ch - 'a');
    }
};
 
std::string replaceWords(const std::vector<std::string>& roots, const std::string& sentence) {
    RootTrie trie;
    for (const auto& root : roots) {
        trie.addRoot(root);
    }
    std::istringstream in(sentence);
    std::string word;
    std::string result;
    while (in >> word) {
        if (!result.empty()) {
            result += ' ';
        }
        result += trie.shortestRoot(word);
    }
    return result;
}
 
int main() {
    std::cout << replaceWords({"cat", "bat", "rat"}, "the cattle was rattled by the battery") << '\n';
    std::cout << replaceWords({"a", "aa", "aaa"}, "aadsfasf absbs bbab cadsfafs") << '\n';
    std::cout << replaceWords({"catt", "cat", "bat", "rat"}, "the cattle was rattled by the battery") << '\n';
    std::cout << replaceWords({"ca", "cat"}, "cat catalog cab") << '\n';
    std::cout << replaceWords({"e", "ea", "eat"}, "eating eat eaten") << '\n';
    std::cout << replaceWords({"cat"}, "ca cat catalog") << '\n';
    std::cout << replaceWords({}, "no roots at all") << '\n';
    std::cout << replaceWords({"xyz"}, "") << "|\n";
    try {
        std::cout << replaceWords({"ab"}, "ab a1") << '\n';
    } catch (const std::invalid_argument& e) {
        std::cout << "error: " << e.what() << '\n';
    }
    return 0;
}

Compile and run it:

g++ -std=c++20 -Wall -o replace replace.cpp && ./replace

Output:

the cat was rat by the bat
a a bbab cadsfafs
the cat was rat by the bat
ca ca ca
e e e
ca cat cat
no roots at all
|
error: not a lowercase letter: 1

Here is what the first line does. The roots are cat, bat and rat. The word cattle walks c, a, t. At t the end flag is set, so the function returns cat. The word rattled returns rat, and battery returns bat. The words the, was and by never reach a flag, so they are returned unchanged.

Notice where the cost goes. replaceWords builds the trie once, from the roots, and then walks it once for each word of the sentence. If you had many sentences to process with the same roots, you would keep the trie and call only the walk for each new sentence. The build step is paid once, and each word then costs about its own length. The addRoot loop and the shortestRoot loop have the same shape, one step per letter, which is why the code is short.

The second worked example: a root that is also a longer root

The second line uses the roots a, aa and aaa. Every word that starts with aa also starts with a, so the shortest root is always a. The output shows that. aadsfasf becomes a, and absbs becomes a, even though aa and aaa are also stored. The walk stops at the first a because that node has its end flag set.

Words such as bbab and cadsfafs have no root that starts them, so the walk leaves the trie at the first missing child and returns the word.

The third line shows the effect of a longer root. Adding catt to the list does not change the answer for cattle, because cat is shorter and is found first. The word catt would be replaced by cat, not kept as catt, if it appeared in a sentence.

The third worked example: roots that stop early

Now take the roots ca and cat, and the sentence cat catalog cab. Walk each word.

• cat: the walk goes c, then a. The node for ca has its end flag set. The result is ca.
• catalog: the walk again stops at ca. The result is ca.
• cab: the same. The result is ca.

The output line for this input is ca ca ca. The root cat is never used, because a shorter root is always found first. This is the rule the trie walk makes easy to see.

The last sentence example in the program uses the single root cat and the sentence ca cat catalog. The output is ca cat cat.

• ca is shorter than the root cat. The walk reaches the end of the word after c and a, and the node for ca has no end flag. The loop ends, and the function returns the word itself, ca.
• cat matches the root exactly. The walk stops at the node for cat, and the result is cat.
• catalog returns cat at the same point.

The shortestRoot function has no special case for this. The loop checks each letter's node and the flag after it. When the word runs out first, the loop stops and the function returns the whole word.

A third example with a nested set of roots

Use the roots e, ea and eat. The sentence is eating eat eaten. The output is e e e, because every word starts with e, and e is the shortest root. The longer roots ea and eat are stored, but they are never used for these words. A shortest-root rule always picks e in this case.

The lesson is that the replacement is decided by the first flag on the walk, not by the longest match. If you want the longest root instead, the trie code would have to keep walking after a flag and remember the last one it saw. That is a different problem, and the mistakes section shows what happens when the two are mixed up.

Edge cases to check

Three cases come up often.

1. A word with no root. The walk leaves the trie at the first missing child and returns the word. The program above returns no roots at all unchanged when the root list is empty.
2. An empty sentence. The loop while (in >> word) never runs, so the result is an empty string. The program prints only |.
3. A word that is shorter than every root. The walk reaches the end of the word and returns it unchanged. The ca case above is an example.

The code does not treat an empty root specially. A root of length zero would set the end flag on the trie's top node, but the loop in shortestRoot starts checking flags only after it reads the first letter, so an empty root never matches. The problem statement you will usually see says roots have length at least one, so this case does not arise.

Common mistakes

Mistake 1: keeping the longest root

A common wrong version keeps going after it finds a root, and keeps the last root it saw. Here is a version that works by comparing strings instead of using a trie. It has the same bug as a trie walk that does not stop at the first flag.

#include <iostream>
#include <string>
#include <vector>
 
std::string longestRootBug(const std::vector<std::string>& roots, const std::string& word) {
    std::string best = word;
    for (const auto& root : roots) {
        if (word.rfind(root, 0) == 0) {
            best = root;
        }
    }
    return best;
}
 
int main() {
    std::cout << longestRootBug({"a", "aa", "aaa"}, "aadsfasf") << '\n';
    std::cout << longestRootBug({"ca", "cat"}, "cattle") << '\n';
    return 0;
}

The output is:

aa
cat

The correct answers are a and ca. The bug is that the loop overwrites best each time it finds a matching root. The last matching root is the longest one only if the roots are listed in increasing order of length, which is not guaranteed. The fix is to stop at the first match, or in the trie version, to return as soon as isEnd is true.

Mistake 2: forgetting an include

The code uses std::istringstream, which lives in the <sstream> header. If that include is missing, the compiler reports the error below. This is the real output from g++ 15.2.0, with the include line removed from the program above and -std=c++20 -Wall set:

replace_nosstream.cpp: In function ‘std::string replaceWords(const std::vector<std::__cxx11::basic_string<char> >&, const std::string&)’:
replace_nosstream.cpp:60:35: error: variable ‘std::istringstream in’ has initializer but incomplete type
   60 |     std::istringstream in(sentence);
      |                                   ^

The fix is to add #include <sstream>. The message is confusing because it names the variable and not the header. When you see "incomplete type" for a standard class, check the includes first.

Mistake 3: returning an empty string for a missing root

A beginner may write return ""; when no root matches, which deletes the word from the sentence. The rule says to keep the word. The return std::string(word); at the end of shortestRoot is what keeps unmatched words, and the break in the loop sends the walk there when a child is missing.

Mistake 4: treating spaces as part of the word

The code reads the sentence with in >> word. The >> operator skips any amount of spaces between words, so the output joins the words with exactly one space. If you read with std::getline and split on a single space character, two spaces in a row would produce an empty word, and the output would contain an empty word between them. The sentence rule in this lesson assumes single spaces, so the >> version matches it.

Practice

Exercise 1

Roots: ill, i. Sentence: illness is ill. Give the output.

Show the answer

i i i. Every word starts with i, and i is the shortest root. The walk for illness stops at the node for i, which has its end flag set.

Exercise 2

Roots: hop, hope. Sentence: hopeful hop hoping. Give the output, and explain why hope is never used.

Show the answer

hop hop hop. The walk for hopeful reaches h, o, p, and the node for hop has its end flag set, so it stops there. The word hope is longer than hop, so the shortest-root rule never picks it.

Exercise 3

Roots: dog, do, cat. Sentence: dogs do cat cats. Give the output.

Show the answer

do do cat cat. The word dogs starts with do, which is a root and is shorter than dog, so do is the answer. The word do is equal to the root do. The word cat is equal to its root. The word cats starts with cat.

Exercise 4

Write a version of shortestRoot that returns the longest root instead of the shortest one. Describe in two sentences what changes in the loop.

Show the answer

The function must keep a variable that stores the length of the last flag it saw, and it must not return at the first flag. It keeps walking until the trie runs out or the word runs out, and then returns the substring for the saved length, or the word if no flag was seen. The loop no longer returns at the first flag, but at the end.

Exercise 5

Explain what happens when shortestRoot is called with the word ca and the single root cat. Name the line that returns the answer.

Show the answer

The loop moves to the node for c, then to the node for a. Neither node has its end flag set. The loop ends because i reaches the end of the word, and the last line return std::string(word); returns ca. No line returns early, so the function returns the whole word.

Summary

• A root is a short word that other words start with. The task is to replace each word with its shortest root.
• A trie walk along a word's letters stops at the first node whose end flag is set, which is the shortest root.
• If the walk leaves the trie or the word runs out before a flag, the word is returned unchanged.
• Keeping the last or longest match is a common bug, and it gives the wrong answer for words such as catalog with roots ca and cat.
• The sentence is split with >>, which skips extra spaces, and the output joins the words with single spaces.