#2047

Easy

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

Number of Valid Words in a Sentence

Count all valid words in a sentence by analyzing each token with precise string-driven validation rules efficiently.

Problem Statement

You are given a sentence containing lowercase letters, digits, hyphens, punctuation marks (!, ., ,), and spaces. A token is defined as a substring separated by one or more spaces.

A token counts as a valid word if it contains no digits, contains at most one hyphen not at the start or end, and contains at most one punctuation mark, which must appear only at the end. Return the total number of valid words in the sentence.

Examples

Example 1

Input: sentence = "cat and dog"

Output: 3

The valid words in the sentence are "cat", "and", and "dog".

Example 2

Input: sentence = "!this 1-s b8d!"

Output: 0

There are no valid words in the sentence. "!this" is invalid because it starts with a punctuation mark. "1-s" and "b8d" are invalid because they contain digits.

Example 3

Input: sentence = "alice and bob are playing stone-game10"

Output: 5

The valid words in the sentence are "alice", "and", "bob", "are", and "playing". "stone-game10" is invalid because it contains digits.

Constraints

1 <= sentence.length <= 1000
sentence only contains lowercase English letters, digits, ' ', '-', '!', '.', and ','.
There will be at least 1 token.

Solution Approach

Split Sentence into Tokens

Iterate through the sentence and split it by spaces to extract each token. Ignore empty strings to prevent counting extra spaces as invalid words.

Validate Each Token

For every token, check three conditions: it must not contain digits, it can have at most one internal hyphen, and at most one punctuation mark at the end. Count it only if all conditions pass.

Accumulate and Return Result

Keep a running counter for valid tokens and return it at the end. This ensures linear time processing relative to sentence length, avoiding unnecessary string rebuilds.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) where n is the sentence length, as each character is inspected once. Space complexity is O(n) due to storing tokens during splitting and temporary variables for validation.

What Interviewers Usually Probe

Look for whether the candidate efficiently splits the sentence without extra string rebuilds.
Check if they correctly enforce hyphen and punctuation placement rules per token.
Notice if the candidate avoids counting empty tokens caused by multiple spaces.

Common Pitfalls or Variants

Common pitfalls

Failing to ignore multiple consecutive spaces leads to miscounting empty tokens as invalid words.
Allowing digits or misplaced hyphens within tokens, which violates the problem's strict word definition.
Placing punctuation anywhere except the end of a token and still counting it as valid.

Follow-up variants

Count valid words ignoring case sensitivity or extended Unicode characters.
Return the list of valid words instead of just the count.
Validate words with multiple allowed punctuation marks or special symbols.

FAQ

What defines a valid word in the Number of Valid Words in a Sentence problem?

A valid word contains no digits, at most one hyphen not at the start or end, and at most one punctuation mark located at the end.

Can multiple consecutive spaces affect the word count?

Yes, you must ignore empty tokens created by consecutive spaces to avoid counting them as invalid words.

Is a token with a hyphen at the start or end considered valid?

No, a valid token may have at most one hyphen and it must be internal, not at the beginning or end.

Should punctuation appear anywhere in a valid word?

No, punctuation is allowed at most once and only at the end of the token according to the problem rules.

What is the recommended approach pattern for solving this problem?

Use a string-driven solution pattern: split the sentence into tokens and validate each based on digits, hyphens, and punctuation placement.

terminal

Solution

Solution 1: Simulation

First, we split the sentence into words by spaces, and then check each word to determine if it is a valid word.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def countValidWords(self, sentence: str) -> int:
        def check(s: str) -> bool:
            st = False
            for i, c in enumerate(s):
                if c.isdigit() or (c in "!.," and i < len(s) - 1):
                    return False
                if c == "-":
                    if (
                        st
                        or i in (0, len(s) - 1)
                        or not s[i - 1].isalpha()
                        or not s[i + 1].isalpha()
                    ):
                        return False
                    st = True
            return True

        return sum(check(s) for s in sentence.split())

Continue Practicing

#2042 check if numbers are ascending in a sentence #2053 kth distinct string in an array #2055 plates between candles