2047. Number of Valid Words in a Sentence LeetCode Solution

In this guide, you will get 2047. Number of Valid Words in a Sentence LeetCode Solution with the best time and space complexity. The solution to Number of Valid Words in a Sentence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Number of Valid Words in a Sentence solution in C++
Number of Valid Words in a Sentence solution in Java
Number of Valid Words in a Sentence solution in Python
Additional Resources

2047. Number of Valid Words in a Sentence LeetCode Solution image

Problem Statement of Number of Valid Words in a Sentence

A sentence consists of lowercase letters (‘a’ to ‘z’), digits (‘0’ to ‘9’), hyphens (‘-‘), punctuation marks (‘!’, ‘.’, and ‘,’), and spaces (‘ ‘) only. Each sentence can be broken down into one or more tokens separated by one or more spaces ‘ ‘.
A token is a valid word if all three of the following are true:

It only contains lowercase letters, hyphens, and/or punctuation (no digits).
There is at most one hyphen ‘-‘. If present, it must be surrounded by lowercase characters (“a-b” is valid, but “-ab” and “ab-” are not valid).
There is at most one punctuation mark. If present, it must be at the end of the token (“ab,”, “cd!”, and “.” are valid, but “a!b” and “c.,” are not valid).

Examples of valid words include “a-b.”, “afad”, “ba-c”, “a!”, and “!”.
Given a string sentence, return the number of valid words in sentence.

Example 1:

Input: sentence = “cat and dog”
Output: 3
Explanation: The valid words in the sentence are “cat”, “and”, and “dog”.

Example 2:

Input: sentence = “!this 1-s b8d!”
Output: 0
Explanation: 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
Explanation: 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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

2047. Number of Valid Words in a Sentence LeetCode Solution in C++

class Solution {
 public:
  int countValidWords(string sentence) {
    int ans = 0;
    istringstream iss(sentence);

    for (string token; iss >> token;)
      if (isValid(token))
        ++ans;

    return ans;
  }

 private:
  bool isValid(const string& token) {
    int countHyphen = 0;
    for (int i = 0; i < token.length(); ++i) {
      const char c = token[i];
      if (isdigit(c))
        return false;
      if (c == '-') {
        if (i == 0 || !isalpha(token[i - 1]))
          return false;
        if (i + 1 == token.length() || !isalpha(token[i + 1]))
          return false;
        if (++countHyphen > 1)
          return false;
      } else if (c == '!' || c == '.' || c == ',') {
        if (i != token.length() - 1)
          return false;
      }
    }
    return true;
  }
};
/* code provided by PROGIEZ */

2047. Number of Valid Words in a Sentence LeetCode Solution in Java

class Solution {
  public int countValidWords(String sentence) {
    int ans = 0;

    for (final String token : sentence.trim().split("\\s+"))
      if (isValid(token))
        ++ans;

    return ans;
  }

  private boolean isValid(final String token) {
    int countHyphen = 0;
    for (int i = 0; i < token.length(); ++i) {
      final char c = token.charAt(i);
      if (Character.isDigit(c))
        return false;
      if (c == '-') {
        if (i == 0 || !Character.isLowerCase(token.charAt(i - 1)))
          return false;
        if (i + 1 == token.length() || !Character.isLowerCase(token.charAt(i + 1)))
          return false;
        if (++countHyphen > 1)
          return false;
      } else if (c == '!' || c == '.' || c == ',') {
        if (i != token.length() - 1)
          return false;
      }
    }
    return true;
  }
}
// code provided by PROGIEZ

2047. Number of Valid Words in a Sentence LeetCode Solution in Python

class Solution:
  def countValidWords(self, sentence: str) -> int:
    def isValid(token: str) -> bool:
      countHyphen = 0
      for i, c in enumerate(token):
        if c.isdigit():
          return False
        if c == '-':
          if i == 0 or not token[i - 1].isalpha():
            return False
          if i == len(token) - 1 or not token[i + 1].isalpha():
            return False
          if countHyphen == 1:
            return False
          countHyphen += 1
        if c in ['!', '.', ',']:
          if i != len(token) - 1:
            return False
      return True

    return sum(isValid(token) for token in sentence.split())
 # code by PROGIEZ