You are given a string and a number k. You need to right shift the string k times. What is the efficient way to solve this?
Example:
the string is "Democracy".
If k is 2, then the output should be "cyDemocra".
If k is 3, then the output should be "acyDemocr"
Answer 1:
O(nk) time complexity, O(1) space complexity.
where n is the length of the string.
Right shift the string k times.
main() { char s[] = "Some string ...."; int n = streln(s); for(int i=0; i<k; i++) rightShift(s, n); } rightShift(char s[], int length) { char temp = s[length-1]; for(int i=length-1; i>0; i--) s[i]=s[i-1]; s[0] = temp; }
Answer 2:
O(n) time complexity, and O(k) space complexity
char s[] = "Some string ...."; int n = streln(s); char *exsp = (char*)calloc(k, sizeof(char)); for(int i=0; i<k; i++) exsp[i]=s[n-k+i]; for(int i=n-1; i>=k; i--) s[i]=s[i-k]; for(int i=0; i<k; i++) s[i]=exsp[i];
Answer 3:
O(n) time complexity, O(1) space complexity
Reverse the entire array.
Reverse the array from 0 to k-1, and from k-1 to n-1.
Reverse(char s[], int start, int end) { for(int i=start, j=end; i<j; i++, j--) { int t=s[i]; s[i]=s[j]; s[j]=t; } } Reverse(s, 0, n-1); Reverse(s, 0, k-1); Reverse(s, k, n-1);
Answer 3 is not O(n) time complexity but O(n^2) time complexity
ReplyDeleteHow is it O(n^2) time complexity? The for loop executes at max n iterations only. So, it is O(n) only.
ReplyDelete