Leetcode – Check if Numbers Are Ascending in a Sentence Solution

Spread the love

In this article, we’ll deep dive into solving a string and number manipulation problem on Leetcode called “Check if Numbers Are Ascending in a Sentence”.

1. Problem Statement

The problem asks us to determine whether the numbers that appear in a given sentence are in strictly ascending order. The sentence is a string containing words separated by single spaces, and a word may contain letters, digits, or both.

2. Understanding the Problem

For instance, if the input sentence is “hello world 5 8 mountain 11”, the numbers in this sentence are 5, 8, and 11. Since they are in strictly ascending order, the function should return True. Otherwise, it should return False.

3. Problem Constraints

  • The input string length is between 1 and 100.
  • The string consists of printable ASCII characters.

4. A Naive Approach

A simple method would be to:

  1. Tokenize the sentence into words.
  2. Identify the numbers among the tokens.
  3. Check if they are in ascending order.

Python Code:

def areNumbersAscending(s: str) -> bool:
    words = s.split(" ")
    prev_num = float('-inf')
    for word in words:
        if word.isdigit():
            curr_num = int(word)
            if curr_num <= prev_num:
                return False
            prev_num = curr_num
    return True

5. Optimized Approaches

5.1 Using Regular Expressions

Python’s re module can help you extract all the numbers with one line of code. Once you have the numbers, you can easily check if they are in ascending order.

5.2 Two-pointer Technique

Alternatively, we can use a two-pointer technique to avoid splitting the string entirely and save on space.

6. Python Code

Using Regular Expressions

import re

def areNumbersAscending(s: str) -> bool:
    numbers = [int(x) for x in re.findall(r'\b\d+\b', s)]
    return all(x < y for x, y in zip(numbers, numbers[1:]))

Two-pointer Technique

def areNumbersAscending(s: str) -> bool:
    prev_num = float('-inf')
    n = len(s)
    i = 0
    while i < n:
        num = 0
        while i < n and s[i].isdigit():
            num = num * 10 + int(s[i])
            i += 1
        if num != 0:
            if num <= prev_num:
                return False
            prev_num = num
        i += 1
    return True

7. Time and Space Complexity

  • Naive Approach: O(N) Time, O(N) Space
  • Using Regular Expressions: O(N) Time, O(N) Space
  • Two-pointer Technique: O(N) Time, O(1) Space

8. Conclusion

Solving the “Check if Numbers Are Ascending in a Sentence” problem offers an excellent opportunity to practice string manipulation and number extraction in Python. The optimized approaches bring either a space advantage or simplify the code.

Leave a Reply