If you want to understand today , you have to search yesterday.

如果你想参透今天，就必须探究昨天。

问题描述

来源：LeetCode第1903题

难度：简单

给你一个字符串num，表示一个大整数。请你在字符串num的所有非空子字符串中找出值最大的奇数，并以字符串形式返回。如果不存在奇数，则返回一个空字符串""。

子字符串是字符串中的一个连续的字符序列。

示例 1

输入：num = "52"

输出："5"

解释：非空子字符串仅有 "5"、"2" 和 "52" 。"5" 是其中唯一的奇数。

示例 2：

输入：num = "4206"

输出：""

解释：在 "4206" 中不存在奇数。

示例 3：

输入：num = "35427"

输出："35427"

解释："35427" 本身就是一个奇数。

提示：

1 <= num.length <= 10^5

num 仅由数字组成且不含前导零

问题分析

这题是让在字符串num的所有非空子串中找出最大的奇数。我们知道只有个位数是奇数（比如1，3，5，7，9），这个数才可能是奇数，如果个位数是偶数，前面无论怎么截取，最终还是偶数。所以如果想把一个数字变为奇数，唯一能改变的就是他的个位数，所以这题思路就很简单了

先判断字符串num最右边的数字是否是奇数：

如果是奇数直接返回

如果不是奇数在判断他的倒数第2位是不是奇数，如果是奇数就从前面截取，如果不是就继续判断倒数第3位……

看下代码

时间复杂度：O(n)，n是字符串的长度，最差情况下都是偶数，遍历所有字符。

空间复杂度：O(1)。


本文原创，未经作者允许不可转载！
更多内容，欢迎关注作者微信公众号：数据结构和算法！