5
\$\begingroup\$

For lack of better things to do I went on coderbyte and did one of the simple challenges since I have not written code for a little while.

The problem was stated as following:

Have the function LongestWord(sen) take the sen parameter being passed and return the largest word in the string. If there are two or more words that are the same length, return the first word from the string with that length. Ignore punctuation and assume sen will not be empty.

Few notes to TL;DR the comments:

  • I would have used const std::string& but function definition was given by CoderByte
  • string[string.length()] is guaranteed to return '\0' since C++11.
  • My code does not look for any terminating zeroes.

I'm looking for more discussion regarding the structure, the approach to the problem and general look & feel.

This is my solution:

// The function definition was given by CoderByte, I would have used     
// const std::string& if it was up to me
string LongestWord(string sen) { 
  // code goes here   
  int start = -1;
  int bstart = -1;
  int blen = 0;

  // lequal since std string is compatible with c strings, it will have \0 at 
  // the end, saving a special case after the loop.
  for (int i = 0; i <= sen.length(); ++i)
  {
      if (start == -1 && isalpha(sen[i]))
      {
          start = i;
      }
      else if (!isalpha(sen[i]))
      {
          if (start >= 0 && i - start > blen)
          {
               blen = i - start;
               bstart = start;
               start = -1;
          }
      }
  }

  return sen.substr(bstart, blen); 
}

I ran the test cases and all was well, so I figured I'd check the top solution on the website:

string LongestWord(string sen) { 

  // code goes here   
  string sen2 = "";
  for(int i=0;i<sen.length();i++)
  {
    if(isalpha(sen[i])||sen[i]==' '||'0'<=sen[i]&&sen[i]<='9')
    {
      sen2.append(sen.substr(i,1));
    }
  }
  char* sench = (char*)sen2.c_str();
  string longest = "";
  int longestLen = 0;
  for(const char* pch=strtok(sench," ");pch;pch=strtok(NULL," "))
  {
    if(strlen(pch)>longestLen)
    {
      longest = pch;
      longestLen=strlen(pch);
    }
  }
  return longest;         
}

From my point of view my solution is less complicated, has fewer moving parts, is easier to digest and at first glance I expect it to perform better due to less looping(although I have not tested this).

I feel like I am missing something, this happens with some frequency where I notice people use more complex solutions and I wonder if I'm basically writing tutorial code or something. Is this just me doubting myself or have I missed something?

\$\endgroup\$
  • \$\begingroup\$ std::string isn't compatible with c strings the way you seem to think it is. std::string can contain several null characters. See: akrzemi1.wordpress.com/2014/03/20/strings-length \$\endgroup\$ – papagaga May 7 at 9:53
  • \$\begingroup\$ Thanks for the comment, I seem to have made some assumptions. It seems assuming that std::string stores a '\0' at the end of the string is the only one that impacts the solution though. \$\endgroup\$ – Peter May 7 at 10:44
  • \$\begingroup\$ While I did not read the standard, some research points towards std::string now being guaranteed to be null terminated and contiguous in memory since C++11. \$\endgroup\$ – Peter May 7 at 11:01
  • \$\begingroup\$ Some research was referring to browsing a bunch of stack overflow questions since I could not come up with anything more definite, see the comment on your answer. \$\endgroup\$ – Peter May 7 at 11:21
  • \$\begingroup\$ @Peter: std::string is probably always null terminated under the hood but the ending null character doesn't have the same meaning as in a C string: it's more convenient with the c_str() interface, but doesn't prevent a std::string to contain intermediary null characters. \$\endgroup\$ – papagaga May 7 at 12:38
4
\$\begingroup\$

Your solution is certainly neater than the other one. Programming challenge websites often contain horrible code.

There's a few things to improve though:


Use the container index type for indexing into a container. This ensures the index values cover the necessary range.

In this case, we should use std::size_t instead of int for indexing the std::string (or std::string::size_type if we're being paranoid). This would mean rethinking the algorithm slightly (perhaps we need a std::optional<std::size_t>).

Note that for storing the difference between indices (i.e. word length) we should use std::ptrdiff_t (or std::string::difference_type).


In C++ it's more idiomatic to use iterators, instead of indices. This makes it easier to genericize functions (e.g. finding the longest run satisfying an arbitrary precondition on an arbitrary sequence).


I'd be inclined to implement this with an outer loop to iterate each word, and an inner loop to find the start and end points.

It's more verbose, but perhaps a bit easier to follow:

#include <algorithm>
#include <cctype>
#include <string>

std::string get_longest_word(std::string const& input)
{
    auto const is_in_word = [] (unsigned char c) { return std::isalpha(c); };

    auto max_word_length = std::string::difference_type{ 0 };
    auto max_word_start = input.end();
    auto max_word_end = input.end();

    for (auto i = input.begin(); i != input.end(); )
    {
        auto word_start = std::find_if(i, input.end(), is_in_word);

        if (word_start == input.end())
            break;

        auto word_end = std::find_if_not(word_start, input.end(), is_in_word);

        auto const word_length = std::distance(word_start, word_end);

        if (word_length > max_word_length)
        {
            max_word_length = word_length;
            max_word_start = word_start;
            max_word_end = word_end;
        }

        i = word_end;
    }

    return std::string(max_word_start, max_word_end);
}

Which is on the way to becoming:

template<InputItT, PredicateT>
std::pair<InputItT, InputItT> find_longest_run(InputItT begin, InputItT end, PredicateT predicate);
\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer. The points about using size_t and ptrdiff_t would be be more robust, instead of setting start to -1 you could simply have a bool to track if we are current inside a word or not. I'm still not quite sold on making the solution more generic though. If I wanted to allow customization of what constitues a word I could add a parameter for a function pointer/functor/interface etc that could optionally replace isalpha. (Should add that the problem is quite specific with no requirements about being approach in a generic way) \$\endgroup\$ – Peter May 7 at 20:19
  • \$\begingroup\$ I see the point about iterators being more idiomatic for modern C++, though I'm not sold on having a for loop that increments the iterator by variable amount based on the word size, it definitely seems more complex to me. the std::find_if and friends mean that I mentally need to parse and understand that each of those will iterate over some part of the string and provide me with new iterators, as opposed to just keeping track of one iterator variable(i). Sorry for being argumentative, it's the only way for me to really take in feedback without being a yes-man. :) \$\endgroup\$ – Peter May 7 at 20:25
3
\$\begingroup\$

The presented solution is quite C-like with strtok and such. For your solution:

  • Your function takes the input by-value, but this seems unnecessary and wasteful. Prefer to take it by const-reference.

  • The idea behind your solution looks OK, but you should notice that std::string can contain multiple null characters and is not null-terminated. In general, I would prefer to solve the problem by leveraging the standard library more. For example, we could write:

    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <cctype>
    
    std::string LongestWord(const std::string& str)
    {
        std::string longest;
    
        for (auto first = str.cbegin(); first != str.cend(); )
        {
            auto w_end = std::adjacent_find(first, str.cend(),
                [](char a, char b)
            {
                return std::isalpha(static_cast<unsigned char>(a)) !=
                    std::isalpha(static_cast<unsigned char>(b));
            });
    
            if (w_end != str.cend())
            {
                ++w_end;
            }
    
            if(std::isalpha(static_cast<unsigned char>(*first)) && 
                std::distance(first, w_end) > longest.size())
            {
                longest = std::string(first, w_end);
            }
    
            first = w_end;
        }
    
        return longest;
    }
    
    int main()
    {
        std::string sen = "Some ,long sentence!!!!! with punctuation \t, and. all that!";
    
        const std::string w = LongestWord(sen);
        std::cout << w << "\n";
    }
    
\$\endgroup\$
  • \$\begingroup\$ @papagaga are you refering to this: For the first (non-const) version, the behavior is undefined if this character is modified to any value other than CharT() . from the cppreference? as far as I can tell that would only be UB if I tried to modify it but maybe I am reading it wrong? Edit: I see what you mean now, it's split up in two, one for pre C++11 where non const is undefined, and one for post C++11 where it is defined. \$\endgroup\$ – Peter May 7 at 12:37
  • 1
    \$\begingroup\$ @Peter: I believe you're right, it's defined after C++11 provided you don't modify the last + 1 character... C++ in all its glory ;-) \$\endgroup\$ – papagaga May 7 at 12:43
  • \$\begingroup\$ Yep. It's nearly impossible to be 100% sure with this god forsaken language. \$\endgroup\$ – Peter May 7 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.