Introduction

In this blog post, we will explore how to solve the LeetCode problem "2047" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 ' '. A token is a valid word if all three of the following are true: It only contains lowercase letters, hyphens, and/or punctuation (no digits). There is at most one hyphen '-'. If present, it must be surrounded by lowercase characters ("a-b" is valid, but "-ab" and "ab-" are not valid). There is at most one punctuation mark. If present, it must be at the end of the token ("ab,", "cd!", and "." are valid, but "a!b" and "c.," are not valid). Examples of valid words include "a-b.", "afad", "ba-c", "a!", and "!". Given a string sentence, return the number of valid words in sentence. Example 1: Input: sentence = "cat and dog" Output: 3 Explanation: The valid words in the sentence are "cat", "and", and "dog". Example 2: Input: sentence = "!this 1-s b8d!" Output: 0 Explanation: There are no valid words in the sentence. "!this" is invalid because it starts with a punctuation mark. "1-s" and "b8d" are invalid because they contain digits. Example 3: Input: sentence = "alice and bob are playing stone-game10" Output: 5 Explanation: The valid words in the sentence are "alice", "and", "bob", "are", and "playing". "stone-game10" is invalid because it contains digits. Constraints: 1 <= sentence.length <= 1000 sentence only contains lowercase English letters, digits, ' ', '-', '!', '.', and ','. There will be at least 1 token.

Explanation

Here's the breakdown of the solution:

• Split the sentence: Split the input sentence into tokens based on spaces.
• Validate each token: Iterate through each token and check if it meets all the criteria for a valid word.

• Count valid words: Increment a counter for each valid word found.

• Runtime Complexity: O(n), where n is the length of the sentence.

• Storage Complexity: O(m), where m is the number of tokens in the sentence (due to the split operation). In the worst case, m could be close to n if the sentence consists of many single-character tokens separated by spaces.

Code

    def countValidWords(sentence: str) -> int:
    """
    Counts the number of valid words in a sentence.

    Args:
        sentence: The input sentence.

    Returns:
        The number of valid words in the sentence.
    """

    tokens = sentence.split()
    count = 0

    for token in tokens:
        if isValidWord(token):
            count += 1

    return count


def isValidWord(token: str) -> bool:
    """
    Checks if a token is a valid word.

    Args:
        token: The token to check.

    Returns:
        True if the token is a valid word, False otherwise.
    """

    hyphen_count = 0
    punctuation_count = 0
    n = len(token)

    for i in range(n):
        char = token[i]

        if char.isdigit():
            return False

        if char == '-':
            hyphen_count += 1
            if hyphen_count > 1:
                return False
            if i == 0 or i == n - 1:
                return False
            if not token[i - 1].islower() or not token[i + 1].islower():
                return False

        if char in ['!', '.', ',']:
            punctuation_count += 1
            if punctuation_count > 1:
                return False
            if i != n - 1:
                return False

        if not char.islower() and char != '-' and char not in ['!', '.', ',']:
            return False

    return True