algoadvance

Leetcode 2047. Number of Valid Words in a Sentence

Problem Statement

You are given a string sentence that consists of lowercase letters, digits, hyphens, punctuation marks ('!', '.', ','), and spaces. You need to count the number of valid words in the sentence.

A valid word is defined as:

  1. It contains only lowercase letters, hyphens, and/or punctuation (no digits).
  2. There is at most one hyphen. If present, it is surrounded by lowercase characters (a-hyphen-b is valid, but hyphen and a-hyphen or hyphen-b are not).
  3. At most one punctuation mark ('!', '.', ','), which must be at the end.

You need to return the number of valid words in the given sentence.

Clarifying Questions

  1. What characters make up the word separators in the sentence?
    • Words are separated by single spaces.
  2. Are leading or trailing spaces in the sentence possible?
    • It is safe to trim leading or trailing spaces before processing.
  3. How should we handle multiple consecutive spaces since they separate words?
    • Treat each sequence of spaces as a single delimiter for words.

Strategy

  1. First, we split the input sentence into individual words using space as a delimiter.
  2. Then, for each word, validate it according to the rules mentioned:
    • Check if it contains any digits.
    • Ensure it has at most one hyphen and the hyphen (if present) is surrounded by lowercase letters.
    • Check for at most one punctuation mark and ensure it is at the end of the word.
  3. Count the number of valid words based on the validation criteria.

Code

#include <iostream>
#include <sstream>
#include <cctype>

bool isValidWord(const std::string& word) {
    int hyphenCount = 0;
    int punctuationCount = 0;
    int n = word.size();

    for (int i = 0; i < n; ++i) {
        char ch = word[i];

        if (std::isdigit(ch)) {
            return false; // Invalid if contains digits
        }

        if (ch == '-') {
            ++hyphenCount;
            if (hyphenCount > 1 || i == 0 || i == n - 1 || !std::islower(word[i - 1]) || !std::islower(word[i + 1])) {
                return false; // Invalid if more than one hyphen or not surrounded by lowercase letters
            }
        }

        if (ch == '!' || ch == '.' || ch == ',') {
            ++punctuationCount;
            if (punctuationCount > 1 || i != n - 1) {
                return false; // Invalid if more than one punctuation mark or not at the end
            }
        }

        if (ch != '-' && ch != '!' && ch != '.' && ch != ',' && !std::islower(ch)) {
            return false; // Invalid if contains unexpected characters
        }
    }
    return true;
}

int countValidWords(const std::string& sentence) {
    std::istringstream ss(sentence);
    std::string word;
    int validWordCount = 0;

    while (ss >> word) {
        if (isValidWord(word)) {
            ++validWordCount;
        }
    }

    return validWordCount;
}

int main() {
    std::string sentence = "cat and  dog";
    std::cout << "Number of valid words: " << countValidWords(sentence) << std::endl;
    return 0;
}

Time Complexity

The time complexity is O(n), where n is the length of the sentence. This is because each word is processed a constant number of times regardless of its length. The space complexity is also O(n) due to the storage of the words split from the sentence.

This approach ensures that each character in the sentence is checked exactly once within the context of its word, providing an efficient solution to the problem.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI