3
\$\begingroup\$

You are given an array of strings sentences, where each sentences[i] represents a single sentence. Return the maximum number of words that appear in a single sentence.

Example
Input: sentences = ["alice and bob love leetcode", "i think so too", "this is great thanks very much"]
Output: 6
Explanation: The first sentence has 5 words, second sentence has 4 words, third sentence has 6 words, so the maximum number of words is 6.

My program:

int mostWordsFound(vector<string>& sentences) {
    int n = sentences.size();
    int max = 0;

    for (int i = 0; i < n; i++) {
        int counter = 0;
        for (int j = 0; j < sentences[i].size(); j++) {
            if (sentences[i][j] == ' ') counter++;
        }
        if (max < counter) max = counter;
    }
    return max + 1;
}

My program's output is correct, but the time complexity is O(n^2), are there any other ways to improve this program? Thanks.

\$\endgroup\$
1
  • \$\begingroup\$ You are assuming words are separated by a single space. Maybe all the test data is; but I would not assume that about real world data. Also you have not considered punctuation will that effect words? \$\endgroup\$ 18 hours ago

1 Answer 1

3
\$\begingroup\$

Time Complexity

First of all, your time complexity is not O(n^2). You only have one loop going from 0 to n and then loop over each character. So your time complexity rather looks like O(n*k). I don't think it can be any faster, since you need to check every string and every character.

Using namespace std

I think it's really terrible that leetcode does this by default. Read this link on why it's considered bad practice.

ref vs const ref

You're taking the array as a ref, but not as a const ref. Since you're not altering it in any way, you should take it as a const ref.

.size() does not return an int

int n = sentences.size();

the return type of std::vector::size() is std::size_t. Converting it to an int might narrow it (for long vectors) and the size can never be negative anyway.

Use range-based for loops

You do not even need to store the size, just use range based for loops:

#include <string>
#include <vector>

int mostWordsFound(std::vector<std::string> const& sentences) {    
    int max = 0;

    for( auto const& sentence : sentences ){
        int counter{0};
        for( auto const& character : sentence ){
            if( character == ' '){
                counter++;
            }
        }
        max = counter > max? counter : max;
    }
    return max+1;    
}

A Bug?

You are assuming that the input somehow makes sense. But consider the following code:

int main(){
    std::cout << mostWordsFound({"Hello World!", "Hello    World\n"}) << "\n";
}

This will output 5, because of all the consecutive whitespaces. A way to improve this program would be to check, if the previous character was a whitespace also, and then not count the current whitespace. Also, trailing or leading whitespaces will give a wrong result (or imagine a string of only spaces!).

\$\endgroup\$
5
  • \$\begingroup\$ In the for loop, why did you use the const& keyword after auto ? \$\endgroup\$
    – user
    Jul 28 at 17:05
  • \$\begingroup\$ If you do not use it, each loop iteration will create a copy. You can also drop the const and just use a ref, if you want to alter elements while iterating. \$\endgroup\$ Jul 28 at 17:09
  • \$\begingroup\$ I think altering elements while iterating is not possible according to this link: stackoverflow.com/questions/6438086/… \$\endgroup\$
    – user
    Jul 28 at 17:13
  • \$\begingroup\$ You understood it wrong. You can alter the elements, but you can not / should not erase or add elements while iterating. See this example here \$\endgroup\$ Jul 28 at 17:19
  • 2
    \$\begingroup\$ Thanks for your help. \$\endgroup\$
    – user
    Jul 28 at 17:24

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.