LT简单题345-反转字符串中的元音字母
题目描述:
给你一个字符串 s ,仅反转字符串中的所有元音字母,并返回结果字符串。
元音字母包括 a、e、i、o、u,且可能以大小写两种形式出现。
示例 1: 输入:s = "hello" 输出:"holle" 示例 2: 输入:s = "leetcode" 输出:"leotcede"
方法一:双指针(C++代码)
class Solution { public: string reverseVowels(string s) { //方法一:双指针 auto isVowel = [vowels = "aeiouAEIOU"s](char ch){ return vowels.find(ch) != string::npos; }; int n = s.size(); int i = 0, j = n - 1; while(i < j){ while(i < n && !isVowel(s[i])){ i++; } while(j > -1 && !isVowel(s[j])){ j--; } if(i < j){ swap(s[i], s[j]); i++; j--; } } return s; } };
时间复杂度:O(n),其中 n 是字符串 s 的长度。在最坏的情况下,两个指针各遍历整个字符串一次。 空间复杂度:O(1) 或 O(n),取决于使用的语言中字符串类型的性质。如果字符串是可修改的,那么我们可以直接在字符串上使用双指针进行交换,空间复杂度为 O(1),否则需要使用 O(n) 的空间将字符串临时转换为可以修改的数据结构(例如数组),空间复杂度为 O(n)。
上一篇:
IDEA上Java项目控制台中文乱码