345. Reverse Vowels of a String

题目描述和难度

  • 题目描述:

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

示例 1:
给定 s = "hello", 返回 "holle".

示例 2:
给定 s = "leetcode", 返回 "leotcede".

注意:
元音字母不包括 "y".

思路分析

求解关键:

参考解答

参考解答1



title: leetcode 345. Reverse Vowels of a String date: 2017-09-23 16:16:36 tags:


  1. Reverse Vowels of a String https://leetcode.com/problems/reverse-vowels-of-a-string/description/

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

Example 1: Given s = "hello", return "holle".

Example 2: Given s = "leetcode", return "leotcede".

Note: The vowels does not include the letter "y".

我的思路

  • 使用指针对撞,遇到元音字符的时候就听下来交换,交换以后指针继续向前;
  • 这样的代码其实是套路,多写几遍就不会忘记了,我们在基础算法的学习中,曾经也有遇到过。

我的解答

Java 代码实现:

public class Solution {
    /**
     * 写多了就知道,这是套路了
     *
     * @param s
     * @return
     */
    public String reverseVowels(String s) {
        if (s.length() == 0) return "";
        char[] chars = s.toCharArray();
        int i = 0;
        int j = chars.length - 1;
        while (true) {
            // 如果走到最后一位都不符号要求的话,就不能再前进了。代码实现如下
            while (i < chars.length && !checkVowels(chars[i])) {
                i++;
            }
            while (j >= 0 && !checkVowels(chars[j])) {
                j--;
            }
            if (i < j) {
                swap(chars, i, j);
                i++;
                j--;
            } else {
                break;
            }
        }
        return new String(chars);
    }

    private void swap(char[] chars, int index1, int index2) {
        if (index1 == index2) return;
        char temp = chars[index1];
        chars[index1] = chars[index2];
        chars[index2] = temp;
    }

    private boolean checkVowels(char c) {
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
                c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U'   ) {
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        //String result1 = solution.reverseVowels("hello");
        //System.out.println(result1);
        //String result2 = solution.reverseVowels("leetcode");
        //System.out.println(result2);

        String result3 = solution.reverseVowels(" ");
        System.out.println(result3);

    }
}

要注意的地方

  • 极端的情况要考虑到:if (s.length() == 0) return "";
  • 还有一种极端的情况要考虑到,就是 i 和 j 可以一直走到底的情况,翻译成大白话就是:如果走到最后一位都不符号要求的话,就不能再前进了。代码实现如下:
while (i < chars.length && !checkVowels(chars[i])) {
    i++;
}
while (j >= 0 && !checkVowels(chars[j])) {
    j--;
}

上述代码特别容易忽略掉:i < chars.lengthj >= 0 这两个前提条件。

上面的写法太臃肿:

class Solution(object):
    def reverseVowels(self, s):
        """
        :type s: str
        :rtype: str
        """

        vowels = set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'])

        s = list(s)

        left = 0
        right = len(s) - 1

        while left < right:
            if s[left] not in vowels:
                left += 1
            elif s[right] not in vowels:
                right -= 1
            else:
                s[left], s[right] = s[right], s[left]
                left += 1
                right -= 1
        return ''.join(s)

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0345-reverse-vowels-of-a-string ,如果我的题解有错误,或者您有更好的解法,欢迎您告诉我 liweiwei1419@gmail.com