Interview Practice 26 - String Right-rotation

Question

Write a program to right-rotate a string by m characters. Right-rotating a string means moving m characters at the left of string to the right. Is it required the time complexity is O(n) and helper memory size is O(1). For example, right-rotate “abcdefghi” by 3 characters gives “defghiabc”.

Solution

There are 2 ways to do it. The first one is that we divide the string into 2 parts (XY). X is the part to move to the right and Y is the one moving on to the left. Reverse them in place 2 times.

XY: "abcdefghi" R(X) R(T): "cbaihgfed" YX: "defghiabc"

Secondly we can swap character one by one. Let p0 at position 0, p1 at position m. Swap their characters repeatedly with moving both pointer right by 1.

abcdefghij dbcaefghij decabfghij defabcghij defgbcahij defghcabij defghiabcj defghijbca <- p1 doesn't move since it reaches the end defghijacb defghijabc

include // reverse the string between start and end void reverse_string(char* start_pointer, char* end_pointer) { while (start_pointer < end_pointer) { char temp_char = start_pointer; start_pointer = end_pointer; end_pointer = temp_char; start_pointer++; end_pointer--; } } // solution 1 void left_rotate_string_1(char string_pointer, int n) { if (string_pointer == NULL) return; int length = strlen(string_pointer); if (n > length || n <= 0) return; char first_start_pointer = string_pointer; char first_end_pointer = string_pointer + n - 1; char second_start_pointer = string_pointer + n; char* second_end_pointer = string_pointer + length - 1; reverse_string(first_start_pointer, first_end_pointer); reverse_string(second_start_pointer, second_end_pointer); reverse_string(first_start_pointer, second_end_pointer); } // solution 2 void left_rotate_string_2(char* string_pointer, int n) { if (string_pointer == NULL) return; int length = strlen(string_pointer); if (n > length || n <= 0) return; char* pointer_1 = string_pointer; char* pointer_2 = string_pointer + n; char* pointer_end = string_pointer + length - 1; while (pointer_1 != pointer_2) { char temp_char = *pointer_1; *pointer_1 = *pointer_2; *pointer_2 = temp_char; if (pointer_1 != pointer_end) pointer_1++; if (pointer_2 != pointer_end) pointer_2++; } } // main int main() { char string_1[] = "abcdefghij"; left_rotate_string_1(string_1, 3); printf("%sn", string_1); // defghijabc char string_2[] = "abcdefghij"; left_rotate_string_2(string_2, 3); printf("%sn", string_2); // defghijabc }

Show Comments