1. Valid Word (LeetCode)
Model answer
The task
Decide whether a string is a valid word: it must have at least three characters, contain only English letters or digits, and include at least one vowel and one consonant.
Key idea
Scan the string once, rejecting any character that is not an ASCII letter or digit. During the scan, track whether a vowel and a consonant have appeared; digits satisfy neither condition.
Approach
- Return
Falseif the string is shorter than three characters. - Initialize flags for whether a vowel and a consonant have been seen.
- For each character, check that it is an ASCII letter or digit.
- For letters, update the appropriate flag, ignoring case.
- Return
Trueonly if both flags are set.
class Solution:
def isValid(self, word: str) -> bool:
if len(word) < 3:
return False
vowels = set("aeiou")
has_vowel = False
has_consonant = False
for char in word:
is_ascii_letter = (
"a" <= char <= "z" or "A" <= char <= "Z"
)
is_ascii_digit = "0" <= char <= "9"
if not is_ascii_letter and not is_ascii_digit:
return False
if is_ascii_letter:
if char.lower() in vowels:
has_vowel = True
else:
has_consonant = True
return has_vowel and has_consonant
Complexity:
- Time: O(n), where
nis the length of the string. - Space: O(1), since the vowel set and tracking flags have fixed size.
Common follow-ups
- How would you handle Unicode letters? Define the permitted character categories explicitly, then use Unicode-aware classification.
- Can you stop early? Yes, once both letter types have appeared, any remaining characters need only be checked for validity.
- What if the vowel set changes? Store the allowed vowels in a configurable set and use the same scan.