Valid Word
EasyPrompt
A word is considered valid if:
- It contains a minimum of 3 characters.
- It contains only digits (0-9), and English letters (uppercase and lowercase).
- It includes at least one vowel.
- It includes at least one consonant.
You are given a string word.
Return true if word is valid, otherwise, return false.
Notes:
'a','e','i','o','u', and their uppercases are vowels.- A consonant is an English letter that is not a vowel.
Example 1:
Input: word = "234Adas"
Output: true
Explanation:
This word satisfies the conditions.
Example 2:
Input: word = "b3"
Output: false
Explanation:
The length of this word is fewer than 3, and does not have a vowel.
Example 3:
Input: word = "a3$e"
Output: false
Explanation:
This word contains a '$' character and does not have a consonant.
Constraints:
1 <= word.length <= 20wordconsists of English uppercase and lowercase letters, digits,'@','#', and'$'.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach leverages a single, powerful regular expression to validate the word against all the given conditions simultaneously. Regular expressions provide a concise and declarative way to define patterns for string matching, making the code compact.
Algorithm
- Define a single regular expression string that combines all the rules: minimum length of 3, alphanumeric characters only, at least one vowel, and at least one consonant.
- Use the
String.matches()method with this regex on the inputword. - Return the boolean result of the
matches()method.
Walkthrough
The core of this approach is to construct a single regular expression that encapsulates all the validation rules. The final check is then a single call to word.matches(regex).
Here's a breakdown of the regex components:
^...$: These are anchors that ensure the entire string must match the pattern, not just a substring.{3,}: This is a quantifier that checks if the word's length is at least 3 characters.[a-zA-Z0-9]: This character class ensures that the word consists only of alphanumeric characters.(?=.*[aeiouAEIOU]): This is a positive lookahead. It asserts that somewhere in the string, there is at least one vowel (case-insensitive), without consuming any characters.(?=.*[[a-zA-Z]&&[^aeiouAEIOU]]): This is another positive lookahead that asserts the presence of at least one consonant. The character class[[a-zA-Z]&&[^aeiouAEIOU]]cleverly defines a consonant as any character that is an English letter but is not a vowel.
Combining these, we get a single regex that validates all conditions in one go.
Algorithm:
- Define a single regular expression string that combines all the rules: minimum length of 3, alphanumeric characters only, at least one vowel, and at least one consonant.
- Use the
String.matches()method with this regex on the inputword. - Return the boolean result of the
matches()method.
class Solution { public boolean isValid(String word) { // The regex combines all conditions: // - {3,} ensures length is at least 3. // - [a-zA-Z0-9] ensures only alphanumeric characters. // - (?=.*[aeiouAEIOU]) is a positive lookahead for at least one vowel. // - (?=.*[[a-zA-Z]&&[^aeiouAEIOU]]) is a positive lookahead for at least one consonant. // [[a-zA-Z]&&[^aeiouAEIOU]] is a character class intersection that matches any character // that is an alphabet but not a vowel. String regex = "^(?=.*[aeiouAEIOU])(?=.*[[a-zA-Z]&&[^aeiouAEIOU]])[a-zA-Z0-9]{3,}$"; return word.matches(regex); }}Complexity
Time
O(N), where N is the length of the word. The Java `matches` method, when using this kind of regex, typically involves a number of passes over the string proportional to the number of lookaheads, but it remains linear in time.
Space
O(1). The space used by the regex engine is related to the pattern's length, which is constant. No extra space proportional to the input string length is required.
Trade-offs
Pros
Very concise and declarative, expressing all validation rules in a single line of code.
Leverages the powerful built-in regex engine, avoiding manual iteration logic.
Cons
Regular expressions can be hard to read, understand, and debug, especially for those not familiar with the syntax.
May have performance overhead compared to a direct iterative approach, although this is negligible for small strings as per the constraints.
This approach involves iterating through the string character by character just once. We use boolean flags to keep track of whether we've found a vowel and a consonant. This is a direct, explicit, and highly efficient method for this problem.
Algorithm
- Check if the length of
wordis less than 3. If so, returnfalse. - Initialize boolean flags
hasVowel = falseandhasConsonant = false. - Iterate over each character
cinword. - For each
c, check if it is an English letter or a digit. If not, returnfalse. - If
cis a letter, check if it is a vowel. - If it is a vowel, set
hasVowel = true. - If it is a letter but not a vowel, it is a consonant. Set
hasConsonant = true. - After the loop finishes, return the result of
hasVowel && hasConsonant.
Walkthrough
The algorithm first performs a quick check on the word's length. If it's less than 3, it's invalid, and we return false immediately.
We then initialize two boolean flags, hasVowel and hasConsonant, to false. We iterate through each character of the input string word. In each iteration, we check the character against the rules:
- Valid Character Check: We verify if the character is a letter or a digit. If not, the word contains a special character and is invalid, so we can stop and return
false. TheCharacter.isLetterOrDigit()method is used for this. - Vowel/Consonant Check: If the character is a letter, we determine if it's a vowel or a consonant. A simple way to check for a vowel is to see if the character exists in a predefined string of vowels (e.g.,
"aeiouAEIOU"). If it's a vowel, we sethasVowel = true. If it's a letter but not a vowel, it must be a consonant, so we sethasConsonant = true.
After iterating through the entire string, the word is valid if and only if both hasVowel and hasConsonant flags have been set to true.
Algorithm:
- Check if the length of
wordis less than 3. If so, returnfalse. - Initialize boolean flags
hasVowel = falseandhasConsonant = false. - Iterate over each character
cinword. - For each
c, check if it is an English letter or a digit. If not, returnfalse. - If
cis a letter, check if it is a vowel. - If it is a vowel, set
hasVowel = true. - If it is a letter but not a vowel, it is a consonant. Set
hasConsonant = true. - After the loop finishes, return the result of
hasVowel && hasConsonant.
class Solution { public boolean isValid(String word) { if (word.length() < 3) { return false; } boolean hasVowel = false; boolean hasConsonant = false; String vowels = "aeiouAEIOU"; for (char c : word.toCharArray()) { if (!Character.isLetterOrDigit(c)) { // Invalid character found return false; } if (Character.isLetter(c)) { if (vowels.indexOf(c) != -1) { hasVowel = true; } else { hasConsonant = true; } } } return hasVowel && hasConsonant; }}Complexity
Time
O(N), where N is the length of the word. We iterate through the string exactly once. Each check inside the loop takes constant time.
Space
O(1). We only use a few boolean variables and a constant-size string for vowels, regardless of the input string's length.
Trade-offs
Pros
Optimal time and space complexity for this problem.
The logic is explicit, straightforward, and easy to follow and debug.
Generally faster in practice than regex-based solutions due to no pattern compilation or engine overhead.
Cons
More verbose and requires writing manual iteration and checking logic compared to a concise regex.
Solutions
Solution
class Solution {public boolean isValid(String word) { if (word.length() < 3) { return false; } boolean hasVowel = false, hasConsonant = false; boolean[] vs = new boolean[26]; for (char c : "aeiou".toCharArray()) { vs[c - 'a'] = true; } for (char c : word.toCharArray()) { if (Character.isAlphabetic(c)) { if (vs[Character.toLowerCase(c) - 'a']) { hasVowel = true; } else { hasConsonant = true; } } else if (!Character.isDigit(c)) { return false; } } return hasVowel && hasConsonant; }}class Solution {public: bool isValid(string word) { if (word.size() < 3) { return false; } bool has_vowel = false, has_consonant = false; bool vs[26]{}; string vowels = "aeiou"; for (char c : vowels) { vs[c - 'a'] = true; } for (char c : word) { if (isalpha(c)) { if (vs[tolower(c) - 'a']) { has_vowel = true; } else { has_consonant = true; } } else if (!isdigit(c)) { return false; } } return has_vowel && has_consonant; }};class Solution: def isValid(self, word: str) -> bool: if len(word) < 3: return False has_vowel = has_consonant = False vs = set("aeiouAEIOU") for c in word: if not c . isalnum(): return False if c . isalpha(): if c in vs: has_vowel = True else: has_consonant = True return has_vowel and has_consonantVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.