the catch being position of special characters (for eg: '?' , ',' , ' ' , '.') should remain intact. input string "hello world, how you?" output "you are, how world hello?". string without special characters, o(n) algorithm reverse each word , reverse entire array, doesn't take consideration special characters.
the best algorithm came follows. traverse array , push each word on top of stack , enqueue special characters on queue. , later, pop elements stack , queue simultaneously , conjoin them form required output.
is there in-place o(n) algorithm? if not, can suggest o(n^2) algorithm no space. assume, cannot use string library functions.
so, here's idea.
1) initial string
"hello world, how you?" 2) reverse string, not include final special characters
"uoy era woh ,dlrow olleh?" 3) reverse words in string
"you how ,world hello?" 4) create iterator (pointer, index, whatever use) start , end of string, increment/deincrement each iterator until hit non-words. non words mean blank space or special character. in case, increasing iterator first come across blank between 'you' , 'are', while decreasing iterator come across blank space between 'world' , 'hello' shown below.
"you how ,world hello?" ^ ^ 5) if there no special characters, continue, if hit special character however. reverse between iterators, including characters point to. below shows when happens
"you how ,world hello?" ^ ^ 6) , see result of reversing this.
"you are, woh world hello?" edit due comment johnchen902
7) reverse substring between these iterators, excluding special character found in step (5).
"you are, how world hello?" 8) return step (5).
i haven't coded yet , tricky explain hope understand
Comments
Post a Comment