{x}
blog image

Check if Numbers Are Ascending in a Sentence

A sentence is a list of tokens separated by a single space with no leading or trailing spaces. Every token is either a positive number consisting of digits 0-9 with no leading zeros, or a word consisting of lowercase English letters.

  • For example, "a puppy has 2 eyes 4 legs" is a sentence with seven tokens: "2" and "4" are numbers and the other tokens such as "puppy" are words.

Given a string s representing a sentence, you need to check if all the numbers in s are strictly increasing from left to right (i.e., other than the last number, each number is strictly smaller than the number on its right in s).

Return true if so, or false otherwise.

 

Example 1:

example-1 
Input: s = "1 box has 3 blue 4 red 6 green and 12 yellow marbles"
Output: true
Explanation: 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
Explanation: The numbers in s are: 5, 5. They are not strictly increasing.

Example 3:

example-3 
Input: s = "sunset is at 7 51 pm overnight lows will be in the low 50 and 60 s"
Output: false
Explanation: 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 Explanation: Check if Numbers Are Ascending in a Sentence

This problem requires checking if the numbers within a sentence are strictly increasing from left to right. The solution involves iterating through the sentence, identifying numbers, and comparing them to the previously encountered number.

Approach:

  1. String Splitting: The input sentence s is split into tokens using space as the delimiter. This separates words and numbers.

  2. Number Identification: For each token, we check if it's a number. This is typically done by examining the first character of the token. If the first character is a digit ('0' to '9'), the token is considered a number.

  3. Integer Conversion and Comparison: If a token is identified as a number, it's converted to an integer using functions like int() (Python), Integer.parseInt() (Java), stoi() (C++), or similar functions in other languages. This integer value is then compared to the previous number encountered (pre). If the current number (cur) is less than or equal to the previous number, the numbers are not strictly increasing, and the function returns false.

  4. Update Previous Number: If the current number is greater than the previous number, the current number becomes the new previous number (pre = cur).

  5. Return True: If the loop completes without finding any non-increasing numbers, it means all numbers are strictly increasing, and the function returns true.

Time Complexity Analysis:

The time complexity is dominated by the string splitting and iteration through the tokens. In the worst case, the sentence has many words and few numbers. The splitting operation usually takes O(n) time, where n is the length of the string, and iterating through the tokens also takes O(n) time. Integer conversion takes constant time for each number. Therefore, the overall time complexity is O(n).

Space Complexity Analysis:

The space complexity depends on the number of tokens created during the string splitting. In the worst-case scenario, where the string consists only of single-character words separated by spaces, the number of tokens can be proportional to the length of the string. The space used to store the previous number (pre) and the current number (cur) is constant. Therefore, the space complexity is O(n) in the worst case, although it can be less if the sentence has fewer tokens.

Code Examples (Python, Java, C++):

The code examples in the provided solution accurately reflect the described approach. Each language uses its own specific string manipulation and integer conversion functions, but the core logic remains the same.

Example Breakdown (Python):

class Solution:
    def areNumbersAscending(self, s: str) -> bool:
        pre = 0  # Initialize the previous number to 0
        for t in s.split():  # Iterate through the tokens
            if t[0].isdigit():  # Check if it's a number
                cur = int(t)  # Convert to integer
                if cur <= pre:  # Compare with the previous number
                    return False  # Not strictly increasing
                pre = cur  # Update the previous number
        return True  # All numbers are strictly increasing

This Python code clearly demonstrates each step: splitting, checking for digits, converting to an integer, comparing, and updating. The other language examples follow a similar structure.