Subscribed unsubscribe Subscribe Subscribe

0w1

CFR 795 K. Stepan and Vowels ( Ad hoc )

Problem - K - Codeforces

題意:
給一個長度為 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