345. Reverse Vowels of a String 反转字符串中的元音字母

作者： 负雪明烛 id： fuxuemingzhu 个人博客： http://fuxuemingzhu.cn/

---

@TOC

[LeetCode]

题目地址：https://leetcode.com/problems/reverse-vowels-of-a-string/

Total Accepted: 7758 Total Submissions: 22132 Difficulty: Easy

题目描述

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:

Input: "hello"
Output: "holle"

Example 2:

Input: "leetcode"
Output: "leotcede"

Note:

• The vowels does not include the letter "y".

题目大意

把一个字符串中所有的元音字母倒序，其他位置不变。

解题方法

使用栈

理解题意很重要啊！

这个题的意思是把收尾向中间走的时候遇到的所有元音字符换位置。也就是说 "abecui"-->"ibucea";

把某个东西进行翻转，很容易想到栈。所以把元音字符进栈，再次遍历的时候遇到元音字符就出栈即可。

class Solution(object):
    def reverseVowels(self, s):
        """
        :type s: str
        :rtype: str
        """
        vstack = []
        for c in s:
            if c in "aeiouAEIOU":
                vstack.append(c)
        res = []
        for c in s:
            if c in "aeiouAEIOU":
                res.append(vstack.pop())
            else:
                res.append(c)
        return "".join(res)

双指针

也就是用双指针的方法。一个从头查找，一个从尾查找。同时判断是否为元音字符，如果两个指针都是落在了元音字符上的时候，交换。别忘了交换位置之后前往下一个地点。

python代码如下：

class Solution(object):
    def reverseVowels(self, s):
        """
        :type s: str
        :rtype: str
        """
        N = len(s)
        res = list(s)
        left, right = 0, N - 1
        while left < right:
            while right >= 0 and res[right] not in "aeiouAEIOU":
                right -= 1
            while left < right and res[left] not in "aeiouAEIOU":
                left += 1
            if left < right:
                res[left], res[right] = res[right], res[left]
            left += 1
            right -= 1
        return "".join(res)

Java代码如下：

public class Solution {
    public String reverseVowels(String s) {
        ArrayList<Character> list=new ArrayList();
        list.add('a');
        list.add('e');
        list.add('i');
        list.add('o');
        list.add('u');
        list.add('A');
        list.add('E');
        list.add('I');
        list.add('O');
        list.add('U');
        
        char[] array=s.toCharArray();
        
        int head=0;
        int tail=array.length-1;
        
        while(head<tail){
            if(!list.contains(array[head])){
                head++;
                continue;
            }
            if(!list.contains(array[tail])){
                tail--;
                continue;
            }
            char temp=array[head];
            array[head]=array[tail];
            array[tail]=temp;
            
            head++;
            tail--;
        }
        
        return new String(array);
    }
}

AC:11ms

C++代码如下：

class Solution {
public:
    string reverseVowels(string s) {
        const int N = s.size();
        int left = 0, right = N - 1;
        while (left < right) {
            while (left < N && !isVowel(s[left])) left ++;
            while (right >= 0 && !isVowel(s[right])) right --;
            if (left < right)
                swap(s[left], s[right]);
            left ++;
            right --;
        }
        return s;
    }
private:
    bool isVowel(char x) {
        string t = "aeiouAEIOU";
        return t.find(x) != string::npos;
    }
};

日期

2016/5/1 20:52:19 2018 年 11 月 21 日 —— 又是一个美好的开始 2018 年 12 月 4 日 —— 周二啦！