Given a sentence containing several words and numbers. Find the largest number among them which does not contain 9. If no such number exists, return -1.
Examples :
Input: sentence="This is alpha 5057 and 97"
Output: 5057 Explanation: 5057 is the only number that does not have a 9.
Input: sentence="Another input 9007"
Output: -1 Explanation: Since there is no number that does not contain a 9,output is -1.
Expected Time Complexity: O(n)
Expected Auxillary Space: O(n)
Constraints:
1<=n<=106
1<=answer<=1018
n is the length of a given sentence.
Approach 01:
-
C++
-
Python
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
long long ExtractNumber(string s) {
stringstream ss(s);
string word;
long long max_number = -1;
while (ss >> word) {
bool contains_nine = false;
long long number = 0;
bool is_number = false;
for (char c : word) {
if (isdigit(c)) {
is_number = true;
if (c == '9') {
contains_nine = true;
break;
}
number = number * 10 + (c - '0');
} else if (is_number) {
break; // End of number in word
}
}
if (!contains_nine && is_number) {
max_number = max(max_number, number);
}
}
return max_number;
}
};
class Solution:
def ExtractNumber(self, s: str) -> int:
max_number = -1
words = s.split()
for word in words:
contains_nine = False
number = 0
is_number = False
for char in word:
if char.isdigit():
is_number = True
if char == '9':
contains_nine = True
break
number = number * 10 + int(char)
elif is_number:
break # End of number in word
if not contains_nine and is_number:
max_number = max(max_number, number)
return max_number