Number of Valid Words in a Sentence - Solution & Explanation

Problem Overview: Given a sentence containing lowercase letters, digits, spaces, hyphens, and punctuation (! , .), count how many tokens are valid words. A valid word contains only lowercase letters, may include at most one hyphen surrounded by letters, and may end with a single punctuation mark. Tokens cannot contain digits.

The challenge is mostly careful string validation. You split the sentence by spaces and verify each token against the rules. The tricky parts are handling the hyphen placement and ensuring punctuation only appears at the end.

Approach 1: Simple Iterative Validation (O(n) time, O(1) space)

Split the sentence into tokens using whitespace and validate each token character by character. Track whether a hyphen or punctuation has already appeared. When iterating, reject the token if you encounter a digit, more than one hyphen, or punctuation in the middle of the word. If a hyphen appears, verify the characters before and after it are lowercase letters. If punctuation appears, ensure it is the final character. This approach uses direct character checks and a few boolean flags, which keeps memory constant.

The key insight: every rule can be validated in a single pass over the token. Since each character is processed exactly once, the total runtime across the sentence is linear. This method relies purely on basic string processing and conditional checks, which makes it fast and easy to implement in languages like C++, Java, or Python.

Approach 2: Regular Expression Matching (O(n) time, O(1) space)

A compact alternative is to encode the rules in a regular expression. After splitting the sentence into tokens, match each token against a pattern describing valid words. A typical pattern allows lowercase letters, an optional internal hyphen surrounded by letters, and an optional punctuation mark at the end. If the token matches the pattern, count it as valid.

This approach shifts the validation logic into the regex engine. The pattern effectively describes the grammar of a valid token, reducing manual checks in code. Performance remains linear relative to the sentence length because each token is matched once. It is especially concise in Python or JavaScript where regex support is straightforward.

Recommended for interviews: The iterative validation approach is usually preferred. It demonstrates that you can translate problem constraints into precise character checks and control flow. The regex solution is elegant but hides the reasoning inside a pattern, which some interviewers consider less explicit. Showing the manual validation first proves you understand the rules; mentioning the regex alternative shows broader familiarity with string parsing techniques.