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
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:
- Tokenize the sentence into words.
- Identify the numbers among the tokens.
- Check if they are in ascending order.
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
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:]))
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
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.