九章演算法 | Amazon 面試題 : 反轉母音字母

撰文 | JZ

專欄 | 九章演算法

題目描述

完成一個函數，讀入一個字元串，把其中的母音字母反轉，返回反轉後的字元串。

Example 1:

s = "hello", 返回 "holle".

Example 2:

s = "leetcode", 返回 "leotcede".

解題思路分析

如果考慮一個更簡單的問題：如何反轉一個字元串，相信大家都能馬上想到演算法，因為我們知道每個位置的字元在反轉後會出現在什麼位置。

方法一 翻轉id

本題中只需要反轉母音字母，同樣的，我們希望知道每個母音字母在反轉後應該出現在什麼位置。因此我們用一個position數組記錄母音字母的位置，然後進行反轉即可。演算法複雜度為O(N)，N是字元串長度。

方法二 兩個指針的方法

本題還有另外一種思路，那就是two pointer。一個指針從前往後掃描，一個指針從後往前掃描，遇到母音字母是進行交換，直到兩個指針相遇，演算法終止。演算法複雜度同樣是O(N)。

參考程序

解題思路分析

這題在所有面試的題目中屬於easy類型的題目，給出時間複雜度為O(N)（N為字元串長度）的演算法可以進入到下一個階段（面試官會給出更難的題目）。

LintCode相關練習

http://www.lintcode.com/zh-cn/problem/reverse-words-in-a-string/

http://www.lintcode.com/zh-cn/problem/reverse-integer/

推薦閱讀：