Number of Valid Words in a Sentence

Problem Description

Given a string sentence, return the number of valid words in sentence. A valid word must contain only lowercase letters, hyphens, and/or punctuation, and must follow specific rules regarding the placement of hyphens and punctuation.

Key Insights

• A token (word) is valid if it contains only lowercase letters, hyphens, and punctuation marks.
• A valid token can have at most one hyphen, which must be surrounded by lowercase letters.
• A valid token can have at most one punctuation mark, which must be at the end of the token.
• Words are separated by spaces, which can be one or more.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the sentence, as we need to traverse each character to validate words. Space Complexity: O(1), as we are using a constant amount of extra space for variables.

Solution

To solve the problem, we can follow these steps:

1. Split the input sentence into tokens using spaces as delimiters.
2. For each token, check if it meets the criteria for a valid word:
   • Check if it contains any digit.
   • Check the number and placement of hyphens.
   • Check for the presence and position of punctuation marks.
3. Count the valid tokens and return the count.

We can utilize string operations and regular expressions to validate the tokens efficiently.

Code Solutions