CFR 795 K. Stepan and Vowels ( Ad hoc )
題意:
給一個長度為 N 的字串,要求進行壓縮,規則如下:
若 "aeiouy" 任意一個字符連續出現兩次以上,則壓縮為一個。
例外是若 'e' 或 'o' 連續出現恰兩次,則不能壓縮。
制約:
The first line contains the integer n (1 ≤ n ≤ 100 000) — the number of letters in the word written by Stepan.
The second line contains the string s which has length that equals to n and contains only lowercase English letters — the word written by Stepan.
解法:
略。
時間 / 空間複雜度:
O( N )
def is_vowel( ch ) vowel = "aeiouy" for i in 0..( vowel.length - 1 ) do if vowel[ i ] == ch then return true end end return false end N = gets.chomp.to_i S = gets.chomp ans = "" prev = '$' ptr = 0 while ptr < N do if not is_vowel( S[ ptr ] ) then ans.concat( S[ ptr ] ) ptr += 1 next # continue の身代わりらしい end nxt = ptr while nxt < N do if S[ nxt ] != S[ ptr ] then break end nxt += 1 end if nxt - ptr == 2 and ( S[ ptr ] == 'e' or S[ ptr ] == 'o' ) then ans.concat( S[ ptr ] ) ans.concat( S[ ptr ] ) else ans.concat( S[ ptr ] ) end ptr = nxt end print ans