Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Count Words in a Sentence

Try it yourself
EasyProblem

Description

Given a sentence s, return how many words it has. A word is a run of characters that aren't spaces. Words are separated by one or more spaces, and s may start or end with spaces, or be nothing but spaces.

Examples

Example 1

Input: s = "the quick brown fox"

Output: 4

Explanation: Four words, one space between each.

Example 2

Input: s = " hi you "

Output: 2

Explanation: Spaces before, between and after don't make words: just hi and you.

Example 3

Input: s = " "

Output: 0

Explanation: Only spaces, so no words.

Example 4

Input: s = "one"

Output: 1

Explanation: A single word with no spaces.

Constraints

  • 1 ≤ s.length ≤ 10^5
  • s consists of English letters, digits, punctuation and spaces (' ')

Editorial

Approach - Count Where Words Start

Intuition

Counting spaces doesn't work: spaces can lead, trail, or come several in a row. But every word has exactly one start, a character that isn't a space with a space, or the start of the string, right before it. Count those and you've counted the words, whatever the spacing.

Python's s.split() with no argument does the same: it splits on runs of spaces and drops the empty pieces, so len(s.split()) is the answer too.

Step-by-Step Explanation

Let's trace Example 2, s = " hi you ":

  1. Index 1: 'h' comes after a space, so a word starts: hi. That's 1.
  2. Index 5: 'y' comes after a space, so a word starts: you. That's 2.
  3. The spaces before, between and after start nothing. Return 2.

Where Words Start — Each word's first character in green, the rest of it in teal.

Algorithm

  1. Start the count at 0.
  2. For each index i: if s[i] isn't a space and i is 0 or s[i - 1] is a space, add 1.
  3. Return the count.

Code

class Solution {
public:
    int countWords(string& s) {
        int words = 0;
        for (int i = 0; i < (int) s.size(); i++) {
            if (s[i] != ' ' && (i == 0 || s[i - 1] == ' ')) words++;
        }
        return words;
    }
};

class Solution:
    def countWords(self, s: str) -> int:
        words = 0
        for i in range(len(s)):
            if s[i] != " " and (i == 0 or s[i - 1] == " "):
                words += 1
        return words

class Solution {
    public int countWords(String s) {
        int words = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != ' ' && (i == 0 || s.charAt(i - 1) == ' ')) words++;
        }
        return words;
    }
}

var countWords = function(s) {
    let words = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] !== " " && (i === 0 || s[i - 1] === " ")) words++;
    }
    return words;
};

Complexity Analysis

Time Complexity: O(n)

Each character is looked at once.

Space Complexity: O(1)

One count.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Counting spaces plus 1. s.count(" ") + 1

On s = " hi you " it returns 5; the answer is 2. One space between each pair of words gives spaces + 1 words, but only then. Spaces before the first word, after the last or several in a row each add 1 more.

Splitting on single spaces. len(s.split(" "))

On s = " hi you " it returns 5; the answer is 2. s.split(" ") cuts at every single space, so two spaces in a row leave an empty string between them, and a leading or trailing space leaves one at the end. s.split(), with no argument, splits on runs of spaces and drops the empty pieces.

Counting a word where it ends. if s[i] == " " and s[i - 1] != " ":

On s = "one" it returns 0; the answer is 1. Counting a word where it ends at a space misses the last one when no space comes after it. Count words where they start instead: a non-space character with a space, or nothing, before it.

Where This Pattern Is Taught

This problem practises one pass over a string, deciding at each character from the one before it. It's taught in Introduction to Strings.