algoadvance

You are given a string sentence that consists of words separated by spaces. Each word contains only lowercase letters, hyphens, and/or punctuation symbols (!, . and ,). A valid word follows these rules:

  1. The word contains only lowercase letters, hyphens, and punctuation symbols.
  2. There is at most one hyphen. If present, it should be surrounded by letters.
  3. There is at most one punctuation symbol. If present, it should be at the end of the word.
  4. The punctuation symbols are limited to ‘!’, ‘.’, and ‘,’.

Implement a function that counts the number of valid words in the given sentence.

Clarifying Questions

  1. Can the sentence be an empty string?
    • Yes, an empty string is valid and contains zero words.
  2. Will there be leading or trailing spaces?
    • Assume input can contain leading or trailing spaces but internal sequences are valid.
  3. Should contractions be handled in any way?
    • No, contractions are not mentioned and should not be included.

Code Strategy

  1. Split the sentence into words using space as the delimiter.
  2. Iterate over each word and apply the validation rules.
  3. Count the number of valid words.

Validation Rules:

  1. Initialize a word as valid.
  2. Check for the presence of one hyphen and ensure it is surrounded by letters.
  3. Check for the presence of one punctuation symbol at the end.
  4. Ensure no other non-lowercase characters are present.

Time Complexity

Code

class Solution:
    def countValidWords(self, sentence: str) -> int:
        def is_valid(word):
            word_len = len(word)
            if word_len == 0:
                return False
            
            has_hyphen = False
            for i, char in enumerate(word):
                if char.isdigit():
                    return False
                
                if char in '.,!':
                    if i != word_len - 1:
                        return False
                
                if char == '-':
                    if has_hyphen or i == 0 or i == word_len - 1:
                        return False
                    if not (word[i - 1].isalpha() and word[i + 1].isalpha()):
                        return False
                    has_hyphen = True
                    
            return True
        
        words = sentence.split()
        valid_word_count = 0
        
        for word in words:
            if is_valid(word):
                valid_word_count += 1
        
        return valid_word_count

# Example usage:
# sol = Solution()
# print(sol.countValidWords("cat and  dog")) # Output: 3
# print(sol.countValidWords("!this  1-s b8d!")) # Output: 0

In this implementation, the is_valid function is responsible for verifying if a word meets the specified criteria. The main countValidWords function iterates through the sentence, splits it into words, and counts the valid words using the helper function.

Try our interview co-pilot at AlgoAdvance.com