问题
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3935 访问。
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
输入: "hello"
输出: "holle"
输入: "leetcode"
输出: "leotcede"
说明:元音字母不包含字母"y"。
Write a function that takes a string as input and reverse only the vowels of a string.
Given s = "hello", return "holle".
Given s = "leetcode", return "leotcede".
Note:The vowels does not include the letter "y".
示例
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3935 访问。
public class Program {
public static void Main(string[] args) {
var s = "holle";
var res = ReverseVowels(s);
Console.WriteLine(res);
s = "leotcede";
res = ReverseVowels2(s);
Console.WriteLine(res);
Console.ReadKey();
}
private static string ReverseVowels(string s) {
//暴力解法
//LeetCode超时未AC
//记录元音字母
var vowels = new List<char>() {
'a','e','i','o','u',
'A','E','I','O','U'
};
//字典记录所有元音字母及位置
var dic = new Dictionary<int, char>();
for(var i = 0; i < s.Length; i++) {
if(vowels.Contains(s[i])) {
dic[i] = s[i];
}
}
//两两前后交换所有元音值
for(var i = 0; i < dic.Count / 2; i++) {
var key1 = dic.ElementAt(i).Key;
var key2 = dic.ElementAt(dic.Count - i - 1).Key;
var swap = dic[key1];
dic[key1] = dic[key2];
dic[key2] = swap;
}
//重新规划元音字符串顺序
var res = new StringBuilder(s);
foreach(var item in dic) {
res[item.Key] = item.Value;
}
//返回结果
return res.ToString();
}
private static string ReverseVowels2(string s) {
//双指针法
//记录元音字母
var vowels = new List<char>() {
'a','e','i','o','u',
'A','E','I','O','U'
};
//转换成 char 数组
//因为 C# 的字符串索引器是只读的，所以这是必须的
var chars = s.ToCharArray();
//前后双指针法
var i = 0;
var j = s.Length - 1;
//循环直到指针碰撞时为止
while(i < j) {
//从左向右找到元音字符
while(i < j && !vowels.Contains(chars[i])) i++;
//从右向左找到元音字符
while(i < j && !vowels.Contains(chars[j])) j--;
//交换它们，注意这里的条件是必须的
if(i < j) {
var swap = chars[i];
chars[i++] = chars[j];
chars[j--] = swap;
}
}
//返回结果
return new string(chars);
}
}以上给出2种算法实现，以下是这个案例的输出结果：
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3935 访问。
hello
leetcode分析：
显而易见，以上2种算法的时间复杂度均为： 。