Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
my solution ( i believe this is an O(N) time complexity solution ) not sure on space complexity

nikita michaelson

Jul 5, 2023

 
class Solution:   
def reverseVowels(self, s: str) -> str:     
  vowels = set(['A','a','E','e','i','I','O','o','U','u'])     
  order = [] # use a list as those are ordered     
  ans = ""     
  for x in s: # for all the letters in the string , if a vowel , store in a list       
   if x in vowels:         
    order.append(x)     
  for x in s: # build new string with the vowels reversed using pop function        
   if x in vowels:        
    ans += order.pop()        
   else:         
    ans +=x       
 return ans

2

0

Comments
Comments
S
saifs a year ago

Space complexity would be O(n), max number of elements in 'order' would be n (case where s is only vowels)

Nabeel Keblawi
Nabeel Keblawia year ago

I did the same solution as you. I used a stack to reverse the vowels because that data structure is Last In, First Out. The last vowel in the original string would now be the first vowel in the new string, and so on. That's why I opted to use a stack like you did, inste...

Jake Nelken
Jake Nelkena month ago

I did this also. My understanding is that since it takes up O(2N) space in the worst case (if the string was entirely vowels, for example) then the two-pointer solution would be better for space. Someone please correct me if I am wrong!