<reponame>joey66666/Codeyard
#
# @lc app=leetcode.cn id=345 lang=python3
#
# [345] 反转字符串中的元音字母
#
# https://leetcode-cn.com/problems/reverse-vowels-of-a-string/description/
#
# algorithms
# Easy (51.80%)
# Likes:    208
# Dislikes: 0
# Total Accepted:    100.6K
# Total Submissions: 188K
# Testcase Example:  '"hello"'
#
# 给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。
# 
# 元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现。
# 
# 
# 
# 示例 1：
# 
# 
# 输入：s = "hello"
# 输出："holle"
# 
# 
# 示例 2：
# 
# 
# 输入：s = "leetcode"
# 输出："leotcede"
# 
# 
# 
# 提示：
# 
# 
# 1 <= s.length <= 3 * 10^5
# s 由 可打印的 ASCII 字符组成
# 
# 
#

# @lc code=start

# 1. Solution1, 遍历统计，Time: O(n), Space: O(m), Runtime: 9%
#   - Space: O(m), `m`: `s`中元音字母数量
#   - 遍历，标记元音，放入数组中，再遍历，遇到元音字母，从数组尾取字母替换
# class Solution:
#     def reverseVowels(self, s: str) -> str:
#         vowel, mark = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'], []
#         for i, c in enumerate(s):
#             if c in vowel:
#                 mark.append([i, c])
#         sList, index = list(s), 0
#         for i, c in enumerate(sList):
#             if len(mark) > 0 and index < len(mark) and i == mark[index][0]:
#                 sList[i] = mark[-(index + 1)][1]
#                 index += 1
#         return "".join(sList)

# 2. Solution2, 双指针，Time: O(logn), Space: O(1), Runtime: 72%
#    - 左指针移动到第一个元音字母，右指针移动最后一个元音字母，交换
#    - 注意边界条件, `i < n, j > 0, i < j`
class Solution:
    def reverseVowels(self, s: str) -> str:
        vowel, n = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'], len(s)
        i, j, sList = 0, n - 1, list(s)
        while i < j:
            while i < n and sList[i] not in vowel:
                i += 1
            while j > 0 and sList[j] not in vowel:
                j -= 1
            if i < j:
                sList[i], sList[j] = sList[j], sList[i]
                i += 1
                j -= 1
        return "".join(sList)


# @lc code=end


#
# @lc app=leetcode.cn id=345 lang=python3
#
# [345] 反转字符串中的元音字母
#
# https://leetcode-cn.com/problems/reverse-vowels-of-a-string/description/
#
# algorithms
# Easy (51.80%)
# Likes:    208
# Dislikes: 0
# Total Accepted:    100.6K
# Total Submissions: 188K
# Testcase Example:  '"hello"'
#
# 给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。
# 
# 元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现。
# 
# 
# 
# 示例 1：
# 
# 
# 输入：s = "hello"
# 输出："holle"
# 
# 
# 示例 2：
# 
# 
# 输入：s = "leetcode"
# 输出："leotcede"
# 
# 
# 
# 提示：
# 
# 
# 1 <= s.length <= 3 * 10^5
# s 由 可打印的 ASCII 字符组成
# 
# 
#

# @lc code=start

# 1. Solution1, 遍历统计，Time: O(n), Space: O(m), Runtime: 9%
#   - Space: O(m), `m`: `s`中元音字母数量
#   - 遍历，标记元音，放入数组中，再遍历，遇到元音字母，从数组尾取字母替换
# class Solution:
#     def reverseVowels(self, s: str) -> str:
#         vowel, mark = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'], []
#         for i, c in enumerate(s):
#             if c in vowel:
#                 mark.append([i, c])
#         sList, index = list(s), 0
#         for i, c in enumerate(sList):
#             if len(mark) > 0 and index < len(mark) and i == mark[index][0]:
#                 sList[i] = mark[-(index + 1)][1]
#                 index += 1
#         return "".join(sList)

# 2. Solution2, 双指针，Time: O(logn), Space: O(1), Runtime: 72%
#    - 左指针移动到第一个元音字母，右指针移动最后一个元音字母，交换
#    - 注意边界条件, `i < n, j > 0, i < j`
class Solution:
    def reverseVowels(self, s: str) -> str:
        vowel, n = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'], len(s)
        i, j, sList = 0, n - 1, list(s)
        while i < j:
            while i < n and sList[i] not in vowel:
                i += 1
            while j > 0 and sList[j] not in vowel:
                j -= 1
            if i < j:
                sList[i], sList[j] = sList[j], sList[i]
                i += 1
                j -= 1
        return "".join(sList)


# @lc code=end
# # @lc app=leetcode.cn id=345 lang=python3 # # [345] 反转字符串中的元音字母 # # https://leetcode-cn.com/problems/reverse-vowels-of-a-string/description/ # # algorithms # Easy (51.80%) # Likes:    208 # Dislikes: 0 # Total Accepted:    100.6K # Total Submissions: 188K # Testcase Example:  '"hello"' # # 给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。 # # 元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现。 # # # # 示例 1： # # # 输入：s = "hello" # 输出："holle" # # # 示例 2： # # # 输入：s = "leetcode" # 输出："leotcede" # # # # 提示： # # # 1 <= s.length <= 3 * 10^5 # s 由 可打印的 ASCII 字符组成 # # # # @lc code=start # 1. Solution1, 遍历统计，Time: O(n), Space: O(m), Runtime: 9% #   - Space: O(m), `m`: `s`中元音字母数量 #   - 遍历，标记元音，放入数组中，再遍历，遇到元音字母，从数组尾取字母替换 # class Solution: #     def reverseVowels(self, s: str) -> str: #         vowel, mark = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'], [] #         for i, c in enumerate(s): #             if c in vowel: #                 mark.append([i, c]) #         sList, index = list(s), 0 #         for i, c in enumerate(sList): #             if len(mark) > 0 and index < len(mark) and i == mark[index][0]: #                 sList[i] = mark[-(index + 1)][1] #                 index += 1 #         return "".join(sList) # 2. Solution2, 双指针，Time: O(logn), Space: O(1), Runtime: 72% #    - 左指针移动到第一个元音字母，右指针移动最后一个元音字母，交换 #    - 注意边界条件, `i < n, j > 0, i < j` # @lc code=end