Question

2042. Check if Numbers Are Ascending in a Sentence

中文文档

Description

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:

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:

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.

Solutions

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.

If the traversal ends, it means that the numbers in the string are strictly increasing, so return true.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string $s$.

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

class Solution {
  public boolean areNumbersAscending(String s) {
    int pre = 0;
    for (var t : s.split(" ")) {
      if (t.charAt(0) <= '9') {
        int cur = Integer.parseInt(t);
        if (pre >= cur) {
          return false;
        }
        pre = cur;
      }
    }
    return true;
  }
}

class Solution {
public:
  bool areNumbersAscending(string s) {
    int pre = 0;
    istringstream is(s);
    string t;
    while (is >> t) {
      if (isdigit(t[0])) {
        int cur = stoi(t);
        if (pre >= cur) {
          return false;
        }
        pre = cur;
      }
    }
    return true;
  }
};

func areNumbersAscending(s string) bool {
  pre := 0
  for _, t := range strings.Split(s, " ") {
    if t[0] <= '9' {
      cur, _ := strconv.Atoi(t)
      if pre >= cur {
        return false
      }
      pre = cur
    }
  }
  return true
}

function areNumbersAscending(s: string): boolean {
  let pre = -1;
  for (const cur of s.split(' ')) {
    if (cur[0] <= '9') {
      const num = Number(cur);
      if (num <= pre) {
        return false;
      }
      pre = num;
    }
  }
  return true;
}

impl Solution {
  pub fn are_numbers_ascending(s: String) -> bool {
    let mut pre = -1;
    for cur in s.split(' ') {
      if cur.as_bytes()[0] <= b'9' {
        let num = cur.parse::<i32>().unwrap();
        if num <= pre {
          return false;
        }
        pre = num;
      }
    }
    true
  }
}

bool areNumbersAscending(char* s) {
  int pre = -1;
  int cur = 0;
  for (int i = 0; s[i]; i++) {
    if (isdigit(s[i])) {
      cur = cur * 10 + s[i] - '0';
    } else {
      if (cur != 0) {
        if (cur <= pre) {
          return 0;
        }
        pre = cur;
        cur = 0;
      }
    }
  }
  if (cur != 0 && cur <= pre) {
    return 0;
  }
  return 1;
}

Solution 2

class Solution:
  def areNumbersAscending(self, s: str) -> bool:
    pre = i = 0
    n = len(s)
    while i < n:
      if s[i].isdigit():
        cur = 0
        while i < n and s[i].isdigit():
          cur = cur * 10 + int(s[i])
          i += 1
        if pre >= cur:
          return False
        pre = cur
      else:
        i += 1
    return True