String Rotation
Problem: Given a string s[0..n] and an index pos, output the rotated string s[pos,pos+1,...n,0,1,..pos].
For example: Input “ABCDEFGH” and pos = 3. Output : “DEFGHABC”.
I noticed that when I “shifted” the smaller potion of string to its correct position, the sub-problem to make larger portion in correct order is in fact the main problem on substring.
For example:
ABCDEFGH -> FGHDEABC
We see here ABC is in correct position and order. The problem now is make “FGHDE” become “DEFGH”. And …
FGHDE is in fact the rotation of DEFGH at the same position 3 !!!
In short, here is the code I wrote:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | void RotateString::rotate(int left, int right, int pos){ if (pos == left) return; shift(left,right,pos); //cout << str << " left: " << left << " right: " << right << " pos:" << pos << endl ; int length1 = pos - left; int length2 = right - pos + 1; if (length1 < length2){ // 2 * pos < left + right + 1 rotate(left,left + length2 - 1, pos); // right = left + legth2 - 1 = left + right - pos >= pos }else rotate(left + length2, right, pos); // right > pos //in two case right always larger than pos and left increases toward pos -> the algo stops when left reaches pos } void RotateString::rotate(string str,int pos){ cout << "str:"<< str << "\t length:" << str.length() <<"\t pos:" << pos << endl; RotateString::str = str; if (pos < str.length()){ rotate(0,str.length()-1,pos); } cout << "rotated string:"<<RotateString::str << endl; } void RotateString::shift(int left, int right,int pos){ if (2*pos > left + right){ for (int i = pos; i <= right; i++){ char temp = str[i]; str[i] = str[i- pos + left]; str[i-pos + left] = temp; } } else{ //notice pos is the start of "right string" not end of "left string" for (int i = pos-1; i >= left;i--){ char temp = str[i]; str[i] = str[right - pos + i + 1]; str[right - pos + i + 1] = temp; } } } |
Another solution is to relate it to the string reversion (“My name is Nam” -> “Nam is name my”). This problem is the special case of string reversion when there are only two words in string and the delimiter is defined as a separated position (pos). In short,
1 2 3 | rorateString(string,0,n,pos) = reverse(string,0,pos-1) &reverse(string,pos,n) &reverse(string,0,n); |
Although both solution is O(n) in runtime, the first solution is more efficient than the second. In the first algorithm, each character is “touched” one time only before being moved to the correct position. In the second algorithm, each character is reversed two times, however.