LeetCode: 1903-Largest Odd Number in String 解題紀錄

題目

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 <= 105
• num only consists of digits and does not contain any leading zeros.

返回字串中最長的奇數子序列，比方說 4206 就是無，而 35427 就是 35427 本身。

---

解題思路

我們可以將這個題目轉換成另外一個視角：什麼是奇數？那就是結尾數字並非 0, 2, 4, 6, 8 的其他數值，就會是奇數。

所以我們要做的事情非常簡單，就是從字串的結尾處開始向開頭找，找到第一個奇數的位置，直接做字串的 slicing。

C++ 範例程式碼

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 範例程式碼

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]

---

References

• 1903. Largest Odd Number in String

---

Read More

• LeetCode 解題紀錄目錄