题目描述
思路
map 替换
代码
双指针
代码

leetcode daily 345. 反转字符串中的元音字母

August 19, 2021

题目描述

编写一个函数,以字符串作为输入,反转该字符串中的元音字母。

 

示例 1:

输入:"hello"
输出:"holle"
示例 2:

输入:"leetcode"
输出:"leotcede"
 

提示:

元音字母不包含字母 "y" 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-vowels-of-a-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

map 替换

两次遍历,

  • 第一次遍历用一个数组 arr 存储所元音字符
  • 第二次遍历替换原数组的元音字符,替换规则,从 arr 逆序替换

代码

/**
 * @param {string} s
 * @return {string}
 */
var reverseVowels = function (s) {
  s = s.split('');

  let vowels = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);
  let arr = [];

  // 第一次遍历
  for (let char of s) {
    if (vowels.has(char)) {
      arr.push(char);
    }
  }

  // 第二次遍历
  let cur = arr.length - 1;
  for (let i = 0; i < s.length; i++) {
    if (vowels.has(s[i])) {
      s[i] = arr[cur--];
    }
  }

  return s.join('');
};
// console.log(reverseVowels('hello'));
  • 时间复杂度: $O(N)$
  • 空间复杂度: $O(N)$

双指针

用两个指针 start, end 分别指向字符串开始与结尾位置,start,end 向中间逼近,当同时遇到元音字符时,替换两个字符

代码

/**
 * @param {string} s
 * @return {string}
 */
var reverseVowels = function (s) {
  s = s.split('');

  let vowels = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);

  let start = 0,
    end = s.length - 1;

  while (start < end) {
    while (start < end && !vowels.has(s[start])) {
      start++;
    }

    while (start < end && !vowels.has(s[end])) {
      end--;
    }

    swap(s, start++, end--);
  }

  return s.join('');
};

function swap(s, a, b) {
  let term = s[a];
  s[a] = s[b];
  s[b] = term;
}
  • 时间复杂度: $O(N)$
  • 空间复杂度: $O(1)$

feiker 少年起而行之