#2042

Easy

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

Check if Numbers Are Ascending in a Sentence

Check if the numbers in a sentence are strictly increasing from left to right using string tokenization.

Problem Statement

You are given a sentence where each token is either a number or a word. The task is to check if all the numbers in the sentence are strictly increasing when read from left to right.

Return true if the numbers are strictly increasing; otherwise, return false. You can assume that each number is positive and does not contain leading zeros.

Examples

Example 1

Input: s = "1 box has 3 blue 4 red 6 green and 12 yellow marbles"

Output: true

The numbers in s are: 1, 3, 4, 6, 12. They are strictly increasing from left to right: 1 < 3 < 4 < 6 < 12.

Example 2

Input: s = "hello world 5 x 5"

Output: false

The numbers in s are: 5, 5. They are not strictly increasing.

Example 3

Input: s = "sunset is at 7 51 pm overnight lows will be in the low 50 and 60 s"

Output: false

The numbers in s are: 7, 51, 50, 60. They are not strictly increasing.

Constraints

3 <= s.length <= 200
s consists of lowercase English letters, spaces, and digits from 0 to 9, inclusive.
The number of tokens in s is between 2 and 100, inclusive.
The tokens in s are separated by a single space.
There are at least two numbers in s.
Each number in s is a positive number less than 100, with no leading zeros.
s contains no leading or trailing spaces.

Solution Approach

Tokenize the Sentence

Start by splitting the input sentence into tokens using spaces as delimiters. Identify which tokens are numbers and store them for further comparison.

Compare Numbers

After extracting the numbers, compare each adjacent pair. If at any point a number is not smaller than the next, return false.

Return the Result

If all the numbers pass the comparison check, return true; otherwise, return false as soon as a failure is detected.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this approach is O(n), where n is the number of tokens in the sentence. Since we are simply iterating over the tokens once to extract and compare the numbers, the space complexity is O(k), where k is the number of numbers in the sentence.

What Interviewers Usually Probe

Check if the candidate efficiently handles string tokenization to extract numbers.
Evaluate how well the candidate compares numbers in sequence.
Observe the candidate's understanding of time and space complexity for string manipulation problems.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the solution with unnecessary data structures.
Misunderstanding the problem by considering non-numeric tokens or failing to account for the number order.
Not handling edge cases, such as repeated numbers or numbers in incorrect order.

Follow-up variants

What if the sentence contains only numbers?
What if the sentence has words that don't contain numbers?
How would the solution change if numbers in the sentence had more than two digits?

FAQ

What is the main approach to solve 'Check if Numbers Are Ascending in a Sentence'?

The main approach is to tokenize the sentence, extract numbers, and then check if they are strictly increasing in sequence.

How can string tokenization help in this problem?

String tokenization allows you to separate the sentence into manageable pieces and isolate numbers for comparison.

What time complexity should I expect for this problem?

The time complexity is O(n), where n is the number of tokens in the sentence.

What happens if numbers in the sentence are not strictly increasing?

If the numbers are not strictly increasing, the function will return false.

Are there any edge cases I should consider?

Edge cases include repeated numbers, numbers out of order, and sentences without enough numbers to compare.

terminal

Solution

Solution 1: Simulation

We can split the string $s$ into several words by spaces. Then, for each word, check if it is a number. If it is a number, convert it to an integer, compare it with the previous number. If it is not strictly increasing, return `false`. Otherwise, assign the current number to the previous number and continue the traversal.

1

2

3

4

5

6

7

8

9

class Solution:
    def areNumbersAscending(self, s: str) -> bool:
        pre = 0
        for t in s.split():
            if t[0].isdigit():
                if (cur := int(t)) <= pre:
                    return False
                pre = cur
        return True

Continue Practicing

#2038 remove colored pieces if both neighbors are the same color #2047 number of valid words in a sentence #2053 kth distinct string in an array