How do you solve Number of Valid Words in a Sentence on LeetCode?

Number of Valid Words in a Sentence (LeetCode #2047) can be solved using Brute Force. The optimal approach is Brute Force with Unknown time complexity and Unknown space complexity. Key insight: We can start by splitting the sentence into tokens based on spaces and then check each token for validity. This approach is straightforward but inefficient as it checks each token individually.

What is the time complexity of Number of Valid Words in a Sentence?

The optimal solution for Number of Valid Words in a Sentence runs in Unknown time and uses Unknown space.

What algorithm or data structure is used to solve Number of Valid Words in a Sentence?

Number of Valid Words in a Sentence uses the following concepts: String. The recommended patterns to study are: Regular Expressions, String Manipulation.

What are the interview tips for Number of Valid Words in a Sentence?

Always clarify the problem statement and constraints before jumping into coding. Think about edge cases and how they might affect your solution. Explain your thought process clearly while coding, as it helps the interviewer understand your approach.

What are common mistakes when solving Number of Valid Words in a Sentence?

Not considering edge cases like tokens with only punctuation or hyphens. Failing to check the position of hyphens and punctuation marks properly.

Number of Valid Words in a Sentence — LeetCode #2047 (Easy)

Tags: String

Related patterns: Regular Expressions, String Manipulation

Brute Force approach

Time complexity: Unknown. Space complexity: Unknown.

We can start by splitting the sentence into tokens based on spaces and then check each token for validity. This approach is straightforward but inefficient as it checks each token individually.

Step 1: Split the sentence into tokens using spaces as delimiters.
Step 2: For each token, check if it meets the validity criteria: contains only valid characters, has at most one hyphen surrounded by letters, and has at most one punctuation mark at the end.
Step 3: Count the number of valid tokens and return the count.

Common Mistakes

Not considering edge cases like tokens with only punctuation or hyphens.
Failing to check the position of hyphens and punctuation marks properly.

Interview Tips

Always clarify the problem statement and constraints before jumping into coding.
Think about edge cases and how they might affect your solution.
Explain your thought process clearly while coding, as it helps the interviewer understand your approach.

#2047

Number of Valid Words in a Sentence

Easy

String↗Regular Expressions↗String Manipulation↗

LeetCode ↗

Approaches

💡

Intuition

Time UnknownSpace Unknown

We can start by splitting the sentence into tokens based on spaces and then check each token for validity. This approach is straightforward but inefficient as it checks each token individually.

⚙️

Algorithm

3 steps

1Step 1: Split the sentence into tokens using spaces as delimiters.
2Step 2: For each token, check if it meets the validity criteria: contains only valid characters, has at most one hyphen surrounded by letters, and has at most one punctuation mark at the end.
3Step 3: Count the number of valid tokens and return the count.

solution.py31 lines

1# Full working Python code
2
3def countValidWords(sentence):
4    tokens = sentence.split()
5    valid_count = 0
6    for token in tokens:
7        if isValid(token):
8            valid_count += 1
9    return valid_count
10
11
12def isValid(token):
13    if not token:
14        return False
15    hyphen_count = token.count('-')
16    if hyphen_count > 1:
17        return False
18    if hyphen_count == 1:
19        hyphen_index = token.index('-')
20        if hyphen_index == 0 or hyphen_index == len(token) - 1:
21            return False
22        if not (token[hyphen_index - 1].islower() and token[hyphen_index + 1].islower()):
23            return False
24    punctuation_count = sum(1 for char in token if char in '!.')
25    if punctuation_count > 1:
26        return False
27    if punctuation_count == 1:
28        if token[-1] not in '!.':
29            return False
30        token = token[:-1]  # Remove punctuation for further checks
31    return all(c.islower() or c == '-' for c in token)

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.