阅读 793

Amazon 面试题 | 反转元音字母

专栏 | 九章算法
网址 | www.jiuzhang.com

题目描述

完成一个函数,读入一个字符串,把其中的元音字母反转,返回反转后的字符串。

Example 1:
s = "hello", 返回 "holle".
Example 2:
s = "leetcode", 返回 "leotcede".

解题思路分析

如果考虑一个更简单的问题:如何反转一个字符串,相信大家都能马上想到算法,因为我们知道每个位置的字符在反转后会出现在什么位置。

方法一 翻转id
本题中只需要反转元音字母,同样的,我们希望知道每个元音字母在反转后应该出现在什么位置。因此我们用一个position数组记录元音字母的位置,然后进行反转即可。算法复杂度为O(N),N是字符串长度。

方法二 两个指针的方法
本题还有另外一种思路,那就是two pointer。一个指针从前往后扫描,一个指针从后往前扫描,遇到元音字母是进行交换,直到两个指针相遇,算法终止。算法复杂度同样是O(N)。

参考程序

解题思路分析
这题在所有面试的题目中属于easy类型的题目,给出时间复杂度为O(N)(N为字符串长度)的算法可以进入到下一个阶段(面试官会给出更难的题目)。


推荐阅读:



欢迎关注我的微信公众号:九章算法(ninechapter)。
精英程序员交流社区,定期发布面试题、面试技巧、求职信息等

九章算法,IT教育领域的深耕者
九章算法,IT教育领域的深耕者