算法修炼之路—【字符串】Leetcode 345 反转字符串中的元音字母

文章目录题目描述思路分析解题代码复杂度分析Github源码 题目描述 编写一个函数，以字符串作为输入，反转该字符串中的元音字母。 示例1： 输入： s = “hello” 输出： “holle” 示例2： 输入： s = “leetcode” 输出： “leotcede” 思路分析 难度是简单 ，我们首先要明确元音字母的涵盖范围{a, e, i, o, u}，之后就是常规的条件判断是否为元音和反转元音字符操作了，这里需要进一步思考的是反转字符，这里我们观察两个示例，发现当交换对的字符均为原因字母时才会触发交换，故我们这里罗列出步骤： 判断字符是否为元音字母； 判断倒序字符是否为元音字母； 若是 在算法修炼之路上，我们经常会遇到各种有趣的编程挑战，其中之一便是LeetCode的第345题——反转字符串中的元音字母。本题目的目标是设计一个函数，接收一个字符串作为输入，然后仅反转其中的元音字母。元音字母包括"a", "e", "i", "o", "u"。 在解决这个问题时，我们首先需要了解题目要求。例如，如果输入字符串为"hello"，输出应为"holle"；如果输入是"leetcode"，则输出应为"leotcede"。这里的关键在于，只有当两个相对的字符都是元音时，它们才应该被交换。 解题思路相对简单。我们可以使用以下步骤来实现： 1. 定义一个集合set，包含所有元音字母。 2. 创建一个字符数组res，复制输入字符串s的所有字符到res，以便我们可以安全地修改它。 3. 使用两个指针i和j，分别从字符串的开始和结束向中间移动。初始时，i=0，j=s.length()-1。 4. 当i小于j时，检查res[i]是否为元音字母，如果是，则检查res[j]是否也是元音字母。如果两个都是元音且它们不相同，就交换这两个字符，然后将i向右移动一位，j向左移动一位。如果res[j]不是元音，仅将j向左移动一位。如果res[i]不是元音，仅将i向右移动一位。 5. 将字符数组res转换回字符串并返回。 以下为解题代码实现： ```java public static String solution(String s) { if (s == null || s.length() < 2) { return s; } Set<Character> set = new HashSet<>(); set.add('a'); set.add('e'); set.add('i'); set.add('o'); set.add('u'); char[] res = s.toCharArray(); for (int i = 0, j = s.length() - 1; i < j;) { if (set.contains(res[i])) { if (set.contains(res[j])) { if (res[i] != res[j]) { char tmpC = res[i]; res[i] = res[j]; res[j] = tmpC; } i++; j--; } else { j--; } } else { i++; } } return new String(res); } ``` 这个解法的时间复杂度是O(n)，因为我们遍历了整个字符串n次，并且进行了与元音字母相关的操作。空间复杂度是O(n)，因为创建了一个字符数组res来保存结果，其大小与输入字符串的长度n成正比。此外，元音字母集合set的空间复杂度是常量级，不随n变化。 在实际编程中，这样的问题有助于提升我们的逻辑思维能力和对字符串处理的理解。通过解决这样的题目，我们可以更好地掌握如何高效地操作字符串，并在面对类似问题时能迅速找到解决方案。如果你想要查看完整的可运行代码或了解更多细节，可以访问GitHub上的源代码文件。