Facebook Pixel

3136. Valid Word

EasyString
Leetcode Link

Problem Description

A word is considered valid if it meets the following criteria:

  • It contains a minimum of 3 characters.
  • It consists only of digits (0-9) and English letters (both 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:

  • The letters 'a', 'e', 'i', 'o', 'u', and their uppercase variants are considered vowels.
  • A consonant is any English letter that is not a vowel.

Intuition

To determine if a word is valid, we address the following tasks systematically:

  1. Length Check: First, we assess if the length of the word is less than 3. If it is, it doesn't satisfy the minimum length requirement and thus returns false.

  2. Character Validation: We then iterate through each character to ensure they are either digits or letters. This ensures the word only consists of alphanumeric characters. If a non-alphanumeric character is found, the function returns false.

  3. Vowel and Consonant Check: During the iteration through the string, we check if there's at least one vowel and one consonant. We use two flags, has_vowel and has_consonant, which are toggled to true upon finding their respective character types. For vowels, we use a predefined set of vowel characters for quick lookup.

  4. Final Validation: After completing the iteration, we confirm that both the has_vowel and has_consonant flags are true. If both are true, the word meets all requirements and is deemed valid, returning true. Otherwise, it returns false.

This approach ensures all the criteria for a valid word are checked efficiently by leveraging condition checks and flags in a single traversal of the string.

Solution Approach

Solution 1: Simulation

The solution uses a straightforward simulation approach to check if the given word meets all the criteria for validity.

  1. Initial Length Check:

    • First, the function checks if the length of the string word is less than 3. If this is the case, the function immediately returns False because the word doesn't have enough characters to be valid.

  2. Variable Setup:

    • Two boolean variables are initialized: has_vowel and has_consonant, both set initially to False.
    • A set vs is created to store all vowels for quick membership checking: set("aeiouAEIOU").

  3. Character Iteration:

    • The function iterates over each character c in the word.
    • For each character:
      • Alphanumeric Check:
        • It checks whether c is alphanumeric using c.isalnum(). If c is not a letter or digit, the function returns False, as the word contains invalid characters.
      • Vowel Check:
        • It checks if c is a vowel by verifying if it is in the set vs. If so, has_vowel is set to True.
      • Consonant Check:
        • If c is alphabetic but not a vowel, then it is a consonant, and has_consonant is set to True.

  4. Final Validation:

    • After the loop, the function checks if both has_vowel and has_consonant are True. If they are, it means the word contains at least one vowel and one consonant, returning True.
    • If either is False, the function returns False because the word does not satisfy all the necessary criteria.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to see how the solution approach works. Consider the word apple.

Step-by-Step Analysis:

  1. Initial Length Check:

    • The word apple has 5 characters, which is greater than the minimum requirement of 3. Thus, we proceed with further checks.

  2. Variable Setup:

    • Initialize has_vowel as False.
    • Initialize has_consonant as False.
    • Set vs as {"a", "e", "i", "o", "u", "A", "E", "I", "O", "U"} for quick vowel checking.

  3. Character Iteration:

    • First character (a):
      • It is alphanumeric and a vowel.
      • Set has_vowel to True.
    • Second character (p):
      • It is alphanumeric and a consonant (not in vs).
      • Set has_consonant to True.
    • Third character (p):
      • It is alphanumeric and a consonant.
      • has_consonant remains True.
    • Fourth character (l):
      • It is alphanumeric and a consonant.
      • has_consonant remains True.
    • Fifth character (e):
      • It is alphanumeric and a vowel.
      • has_vowel remains True.

  4. Final Validation:

    • After processing all characters, both has_vowel and has_consonant flags are True.
    • Since all criteria are met, the function returns True, confirming that apple is a valid word.

Solution Implementation

1class Solution:
2    def isValid(self, word: str) -> bool:
3        # If the word contains less than 3 characters, it cannot be valid.
4        if len(word) < 3:
5            return False
6      
7        # Flags to check if the word contains at least one vowel and one consonant.
8        has_vowel = False
9        has_consonant = False
10      
11        # Set of vowels for quick lookup.
12        vowels_set = set("aeiouAEIOU")
13      
14        # Iterate over each character in the word.
15        for char in word:
16            # If the character is not alphanumeric, the word is invalid.
17            if not char.isalnum():
18                return False
19          
20            # Check if the character is an alphabet.
21            if char.isalpha():
22                # Check if it is a vowel.
23                if char in vowels_set:
24                    has_vowel = True
25                else:  # Otherwise, it must be a consonant.
26                    has_consonant = True
27      
28        # The word is valid if it contains at least one vowel and one consonant.
29        return has_vowel and has_consonant
30
1class Solution {
2    public boolean isValid(String word) {
3        // Return false if the word is too short
4        if (word.length() < 3) {
5            return false;
6        }
7
8        // Initialize flags to check for vowels and consonants
9        boolean hasVowel = false;
10        boolean hasConsonant = false;
11
12        // Create a boolean array to identify vowels: a, e, i, o, u
13        boolean[] isVowel = new boolean[26];
14        for (char c : "aeiou".toCharArray()) {
15            isVowel[c - 'a'] = true;
16        }
17
18        // Iterate through each character in the word
19        for (char c : word.toCharArray()) {
20            // Check if character is alphabetic
21            if (Character.isAlphabetic(c)) {
22                // Check if the character is a vowel
23                if (isVowel[Character.toLowerCase(c) - 'a']) {
24                    hasVowel = true;
25                } else {
26                    hasConsonant = true;
27                }
28            } else if (!Character.isDigit(c)) { // Non-alphanumeric character found
29                return false;
30            }
31        }
32
33        // Return true only if the word contains at least one vowel and one consonant
34        return hasVowel && hasConsonant;
35    }
36}
37
1#include <string>
2#include <cctype>
3
4class Solution {
5public:
6    // Function to check the validity of a given word
7    bool isValid(std::string word) {
8        // A valid word must have at least 3 characters
9        if (word.size() < 3) {
10            return false;
11        }
12
13        // Flags to check the presence of vowels and consonants
14        bool hasVowel = false;
15        bool hasConsonant = false;
16      
17        // Boolean array to mark vowels
18        bool vowelStatus[26] = {false};
19        std::string vowels = "aeiou";
20      
21        // Mark vowels in the boolean array
22        for (char c : vowels) {
23            vowelStatus[c - 'a'] = true;
24        }
25      
26        // Iterate over each character in the word
27        for (char c : word) {
28            if (std::isalpha(c)) { // Check if the character is a letter
29                if (vowelStatus[std::tolower(c) - 'a']) {
30                    hasVowel = true; // The letter is a vowel
31                } else {
32                    hasConsonant = true; // The letter is a consonant
33                }
34            } else if (!std::isdigit(c)) { // Check if the character is not a digit (invalid character)
35                return false;
36            }
37        }
38      
39        // Valid if both a vowel and a consonant are present
40        return hasVowel && hasConsonant;
41    }
42};
43
1// Function to check if the given word is valid according to specified conditions
2function isValid(word: string): boolean {
3    // A valid word must have at least 3 characters
4    if (word.length < 3) {
5        return false;
6    }
7
8    // Variables to keep track of the presence of vowels and consonants
9    let hasVowel = false;
10    let hasConsonant = false;
11
12    // Set of characters representing vowels, including both lowercase and uppercase
13    const vowels = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);
14
15    // Iterate through each character in the word
16    for (const char of word) {
17        // If any character is not alphanumeric, the word is invalid
18        if (!char.match(/[a-zA-Z0-9]/)) {
19            return false;
20        }
21
22        // Check if the character is a letter
23        if (/[a-zA-Z]/.test(char)) {
24            // Check if the letter is a vowel
25            if (vowels.has(char)) {
26                hasVowel = true;
27            } else {
28                // If not a vowel, it must be a consonant
29                hasConsonant = true;
30            }
31        }
32    }
33
34    // The word is valid if it contains at least one vowel and one consonant
35    return hasVowel && hasConsonant;
36}
37

Time and Space Complexity

The time complexity of the code is O(n) where n is the length of the input string word. This is because the function iterates over each character of the string once to check if it contains both a vowel and a consonant.

The space complexity is O(1) because the amount of space used by the algorithm does not depend on the size of the input. The additional space is constant as it uses a set for vowels and a few boolean variables to track state.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More