Published on

The Algorithm Design Manual (3rd) Exercise Solution 'E3-42'

Table of Contents

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 3-42

Question

Reverse the words in a sentence—that is, “My name is Chris” becomes “Chris is name My.” Optimize for time and space.

Solution

Outline

Reverse whole string, then re-reverse each word.
Time complexity: O(n)
Space complexity without the string: O(1)

Code


#include <cassert>
#include <string>

constexpr char SP{' '};

std::string reverse_word_in_sentence(std::string_view sentence) {
    if (!sentence.size()) return "";

    std::string to_rev{sentence};

    auto rev_s_in_rng{[](std::string& s, size_t i_bgn, size_t i_end) {
        auto len{i_end - i_bgn};
        for (size_t i = 0; i < len / 2; i++) {
            auto tmp{s[i_bgn + i]};
            s[i_bgn + i] = s[i_end - i - 1];
            s[i_end - i - 1] = tmp;
        }
    }};

    rev_s_in_rng(to_rev, 0, to_rev.size());

    size_t i_w_start;
    if (to_rev[0] == SP)
        i_w_start = 1;
    else
        i_w_start = 0;
    for (size_t i = 1; i < to_rev.size(); i++) {
        if (to_rev[i] == SP) {
            if (i_w_start + 1 < i) rev_s_in_rng(to_rev, i_w_start, i);
            i_w_start = i + 1;
        }
    }
    if (i_w_start + 1 < to_rev.size())
        rev_s_in_rng(to_rev, i_w_start, to_rev.size());
    return to_rev;
}

int main(int argc, char const* argv[]) {
    assert(reverse_word_in_sentence("") == "");
    assert(reverse_word_in_sentence("a") == "a");
    assert(reverse_word_in_sentence("LongSentenceConsistingOfOneWord") ==
           "LongSentenceConsistingOfOneWord");
    assert(reverse_word_in_sentence("My name is Chris") == "Chris is name My");
    assert(reverse_word_in_sentence(" Apple Grape") == "Grape Apple ");
    assert(reverse_word_in_sentence("  Apple Grape") == "Grape Apple  ");
    assert(reverse_word_in_sentence("Apple Grape ") == " Grape Apple");
    assert(reverse_word_in_sentence(" Apple   Banana   Grape     ") ==
           "     Grape   Banana   Apple ");
    return 0;
}