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

The problem

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 ' '.

Example

Input

sentence = "cat and dog"

Output

3

Explanation

The valid words in the sentence are "cat", "and", and "dog".

Python solution

class Solution:
    def countValidWords(self, sentence: str) -> int:
        def check(s: str) -> bool:
            st = False
            for i, c in enumerate(s):
                if c.isdigit() or (c in "!.," and i < len(s) - 1):
                    return False
                if c == "-":
                    if (
                        st
                        or i in (0, len(s) - 1)
                        or not s[i - 1].isalpha()
                        or not s[i + 1].isalpha()
                    ):
                        return False
                    st = True
            return True

        return sum(check(s) for s in sentence.split())

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 2047. Number of Valid Words in a Sentence is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems