Đề bài
A word puzzle app makes easy scrambles with one rule. Scan each word from left to right. Whenever a vowel (a, e, i, o, u) is directly followed by a consonant (any other letter), swap the two letters and continue scanning after the pair, so a letter is never moved twice. Otherwise move on by one letter.
For example orange: o and r swap to give ro, then scanning continues at a, which swaps with n, then at g, which is not a vowel, and e is the last letter: ronage.
Implement word_scramble(words).
Input
words: The words, in lowercase letters.
Output
Return the scrambled words in the same order. A word with no vowel followed by a consonant comes back unchanged.
Ràng buộc
0 ≤ number of words ≤ 1,000
1 ≤ word length ≤ 30
Ví dụ
Đầu vào:
words = ["orange", "apple"]
Kết quả mong đợi:
expected = ["ronage", "paple"]
Đầu vào:
std::vector<std::string> words = {"orange", "apple"};
Kết quả mong đợi:
std::vector<std::string> expected = {"ronage", "paple"};
Đầu vào:
string[] words = new string[] {"orange", "apple"};
Kết quả mong đợi:
string[] expected = new string[] {"ronage", "paple"};
Giải thích
orange becomes ronage as shown above. In apple, a swaps with p to give pa, then p, l and e stay: paple.
Đầu vào:
words = ["sky", "tea", "eat"]
Kết quả mong đợi:
expected = ["sky", "tea", "eta"]
Đầu vào:
std::vector<std::string> words = {"sky", "tea", "eat"};
Kết quả mong đợi:
std::vector<std::string> expected = {"sky", "tea", "eta"};
Đầu vào:
string[] words = new string[] {"sky", "tea", "eat"};
Kết quả mong đợi:
string[] expected = new string[] {"sky", "tea", "eta"};
Giải thích
sky has no vowels and tea has no vowel before a consonant, so both stay. In eat, e is followed by the vowel a, then a swaps with t: eta.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Work on a mutable copy of the word, like a character array.
Gợi ý 2
After a swap, move the index forward by 2 so the moved letters are not looked at again.
Gợi ý 3
Without a swap, move forward by 1.
Độ phức tạp mong đợi
O(total letters) time, O(longest word) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.