I was asked to write a program for reversing a string in java using brute force method. I wrote the very general answer which uses string length and charAt() in a for loop. This method has O(n) time complexity, so I was asked to reduce its time complexity. We can use two counters, one running from first position of the string and second from last position of the string running till the middle position of the string, construct two reversed substrings which can then be concatenated to produce complete reversed string. But this will give only O(n/2) which is same as O(n). Are there any another approach to reduce the time complexity for the above program?
Please describe your approach in the below comments section.
Is it possible if you can go on doing the reversal process for a smaller substring(using recursion) just the way you do a merge sort.
ReplyDeleteeg: independent=indep+endent
indep=in+dep
in=i+n--->a normal swap could reverse this.
But I believe this too will have O(n) time complexity, as you keep breaking down the string to two letter sets. Are there any other efficient way?
ReplyDelete