C++ function to count all the words in a string

Viewed 81155

I was asked this during an interview and apparently it's an easy question but it wasn't and still isn't obvious to me.

Given a string, count all the words in it. Doesn't matter if they are repeated. Just the total count like in a text files word count. Words are anything separated by a space and punctuation doesn't matter, as long as it's part of a word.

For example: A very, very, very, very, very big dog ate my homework!!!! ==> 11 words

My "algorithm" just goes through looking for spaces and incrementing a counter until I hit a null. Since i didn't get the job and was asked to leave after that I guess My solution wasn't good? Anyone have a more clever solution? Am I missing something?

10 Answers

Here is a single pass, branchless (almost), locale-aware algorithm which handles cases with more than one space between words:

  1. If the string is empty return 0
  2. let transitions = number of adjacent char pairs (c1, c2) where c1 == ' ' and c2 != ' '
  3. if the sentence starts with a space, return transitions else return transitions + 1

Here is an example with string = "A very, very, very, very, very big dog ate my homework!!!!"

 i | 0123456789
c1 | A very, very, very, very, very big dog ate my homework!!!!
c2 |  A very, very, very, very, very big dog ate my homework!!!!
   |  x     x     x     x     x    x   x   x   x  x

Explanation

Let `i` be the loop counter.

When i=0: c1='A' and c2=' ', the condition `c1 == ' '` and `c2 != ' '` is not met
When i=1: c1=' ' and c2='A', the condition is met
... and so on for the remaining characters

Here are 2 solutions I came up with

Naive solution

size_t count_words_naive(const std::string_view& s)
{
    if (s.size() == 0) return 0;
    size_t count = 0;
    bool isspace1, isspace2 = true;
    for (auto c : s) {
        isspace1 = std::exchange(isspace2, isspace(c));
        count += (isspace1 && !isspace2);
    }
    return count;
}

If you think carefully, you will be able to reduce this set of operations into an inner product (just for fun, I don't recommend this as this is arguably much less readable).

Inner product solution

size_t count_words_using_inner_prod(const std::string_view& s)
{
    if (s.size() == 0) return 0;
    auto starts_with_space = isspace(s.front());
    auto num_transitions = std::inner_product(
            s.begin()+1, s.end(), s.begin(), 0, std::plus<>(),
            [](char c2, char c1) { return isspace(c1) && !isspace(c2); });
    return num_transitions + !starts_with_space;
}

I think that will help

the complexty O(n)

#include <iostream>
#include <string>
#include <ctype.h>
using namespace std;


int main()
{
    int count = 0, size;
    string sent;

    getline(cin, sent);

    size = sent.size();

check if the char is in alpha and the next char not in alpha

     for (int i = 0; i < size - 1; ++i) { 
       if (isalpha(sent[i]) && !isalpha(sent[i+1])) { 
            ++count;
        }
     }

if the word in the last of sentence didn't count above so it count here

     if (isalpha(sent[size - 1]))++count;

    cout << count << endl;
     return 0;
}

Efficient version based on map-reduce approach

#include <iostream>
#include <string_view>
#include <numeric>

std::size_t CountWords(std::string_view s) {
    if (s.empty())
        return 0;

    std::size_t wc = (!std::isspace(s.front()) ? 1 : 0);
    wc += std::transform_reduce(
        s.begin(),
        s.end() - 1,
        s.begin() + 1,
        std::size_t(0),
        std::plus<std::size_t>(),
                [](char left, char right) {
        return std::isspace(left) && !std::isspace(right);
    });

    return wc;
}

int main() {
    std::cout << CountWords("  pretty  little octopus "sv) << std::endl;

    return 0;
}
Related