題目
You are given a string num, representing a large integer. Return the largest-valued odd integer (as a string) that is a non-empty substring of num, or an empty string "" if no odd integer exists.
A substring is a contiguous sequence of characters within a string.
Example 1:Input: num = “52” Output: “5” Explanation: The only non-empty substrings are “5”, “2”, and “52”. “5” is the only odd number.
Example 2:Input: num = “4206” Output: “” Explanation: There are no odd numbers in “4206”.
Example 3:Input: num = “35427” Output: “35427” Explanation: “35427” is already an odd number.
Constraints:
1 <= num.length <= 105numonly consists of digits and does not contain any leading zeros.
Simply put, we need to return the longest sub-string and it would be odd number.
Solution
We can change our view: What is odd number? that is the tail of number is not 0, 2, 4, 6 and 8. So what should we do is very clear, we need to find the first odd number from tail to head, and get the number from head to it.
C++ Sample Code
class Solution {
public:
string largestOddNumber(string num) {
// Init
int tail = 0;
unordered_map<char, bool> isEven({
{'0', true},
{'2', true},
{'4', true},
{'6', true},
{'8', true},
});
// Count from the tail
for (int i=num.size()-1; i>=0; --i) {
if (!isEven[num[i]]) {
tail = i + 1;
break;
}
}
return num.substr(0, tail);
}
};Python Sample Code
class Solution:
def largestOddNumber(self, num: str) -> str:
# Init
tail = 0
evens = {
'0': True,
'2': True,
'4': True,
'6': True,
'8': True,
}
# Count from tail
for i in range(len(num)-1, -1, -1):
if not evens.get(num[i], False):
tail = i + 1
break
return num[:tail]