345. Reverse Vowels of a String

https://leetcode.com/problems/reverse-vowels-of-a-string/

本题大意：实现字符串中元音字母的反转。

解题思路：该题多种思路，这里给出两种。

1、用栈存储扫描到的元音字母，然后重新扫描，把栈中的元音字母填入字符串。时间复杂度o(2n)。

代码实现：

 1 class Solution {
 2 public:
 3     string reverseVowels(string s) {
 4         int n = s.length();
 5         stack<char> letter;
 6         for(int i = 0; i < n; i++)
 7         {
 8             if(s[i] == 'a' ||s[i] == 'e' || s[i] == 'i' || s[i] == 'o'||s[i] == 'u' || s[i] == 'A' || s[i] == 'E' || s[i] == 'I'||s[i] == 'O'||s[i] == 'U')
 9             {
10                 letter.push(s[i]);
11             }
12         }
13         for(int i = 0; i < n; i++)
14         {
15             if(s[i] == 'a' ||s[i] == 'e' || s[i] == 'i' || s[i] == 'o'||s[i] == 'u' || s[i] == 'A' || s[i] == 'E' || s[i] == 'I'||s[i] == 'O'||s[i] == 'U')
16             {
17                 s[i] = letter.top();
18                 letter.pop();
19             }
20         }
21         return s;
22     }
23 };

2、优化代码。从前往后扫描找到元音字母，再从后往前扫描找到元音字母，将两者对调。虽说是两个for循环嵌套起来，但是时间复杂度降低为o(n)了。

 1 class Solution {
 2 public:
 3     string reverseVowels(string s) {
 4         int n = s.length();
 5         int flag = n;
 6         for(int i = 0; i < flag; i++)
 7         {
 8             if(s[i] == 'a' ||s[i] == 'e' || s[i] == 'i' || s[i] == 'o'||s[i] == 'u' || s[i] == 'A' || s[i] == 'E' || s[i] == 'I'||s[i] == 'O'||s[i] == 'U')
 9             {
10                 for(int j = flag-1; j > i; j--)
11                 {
12                     if(s[j] == 'a' ||s[j] == 'e' || s[j] == 'i' || s[j] == 'o'||s[j] == 'u' || s[j] == 'A' || s[j] == 'E' || s[j] == 'I'||s[j] == 'O'||s[j] == 'U')
13                     {
14                         char tmp = s[j];
15                         s[j] = s[i];
16                         s[i] = tmp;
17                         flag = j;
18                         break;
19                     }
20                 }
21             }
22         }
23         return s;
24     }
25 };