Problem: Left rotation of a string is to move some leading characters to its tail. Please implement a function to rotate a string.
For example, if the input string is “abcdefg” and a number 2, the rotated result is “cdefgab”.
Analysis: It looks difficult to get rules of left rotation on a string. Fortunately, the 7th problem in this series “Reverse Words in a Sentence” can give us some hints.
If we input a sentence with two words “hello world” for the problem “Reverse Words in a Sentence”, the reversed result should be “world hello”. It is noticeable that the result “world hello” can be viewed as a rotated result of “hello world”. It becomes “world hello” when we move some leading characters of string “hello world” to its ending. Therefore, this problem is quite similar to problem “Reverse Words in a Sentence”.
Let us take a string “abcdefg” as an example. We divide it into two parts: the first part contains the two leading characters “ab”, and the second part contains all other characters “cdefg”. We firstly reverse these two parts separately, and the whole string becomes “bagfedc”. It becomes “cdefgab” if we reverse the whole string, which is the expected result of left rotation with 2.
According to the analysis above, we can see that left rotation of a string can be implemented calling a Reverse function three times to reverse a segment or whole string. The sample code is shown below:
char* LeftRotateString(char* pStr, int n)
{
if(pStr != NULL)
{
int nLength = static_cast<int>(strlen(pStr));
if(nLength > 0 && n > 0 && n < nLength)
{
char* pFirstStart = pStr;
char* pFirstEnd = pStr + n - 1;
char* pSecondStart = pStr + n;
char* pSecondEnd = pStr + nLength - 1;
// Reverse the n leading characters
Reverse(pFirstStart, pFirstEnd);
// Reverse other characters
Reverse(pSecondStart, pSecondEnd);
// Reverse the whole string
Reverse(pFirstStart, pSecondEnd);
}
}
return pStr;
}
The function Reverse is shown in “Reverse Words in a Sentence”, so we are not going to repeat it here.
The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.
Hello
ReplyDeleteThe solution mentioned is not a completely optimized one. It has the time complexity of O(N),
but this problem can be solved with O(1) time complexity.
String LeftRotateString(int n)
{
String str = "abcdefg";
str = str + "abcdefg"; //Append same string
return str.substr(n,str.length);
}
actually, i think stl append also took O(n) time to copy the original string. So your solution is still O(n). Although, seems more elegant.
DeleteThe solution looks more elegant, but it uses more memory to append same string. The solution in the post rotate strings in place.
DeleteString LeftRotateString(int n)
Delete{
String str = "abcdefg";
str = str + "abcdefg"; //Append same string
return str.substr(n,str.length);
}
O/P of this will be, If n =2
cdefgabcdefg
This will work-->
String LeftRotateString(int n)
{
String str = "abcdefg";
String concatStr = str + "abcdefg"; //Append same string
return concatStr.substring(n,str.length + n);
}
static void rotate(int rotate, String input)
ReplyDelete{
char[] array = input.toCharArray();
int n = array.length;
int count = 0;
int r = n - 1;
int l = rotate - 1;
while(true)
{
if(count == n - 1)
{
break;
}
for(int i = l ; i >= 0; i--)
{
char temp = array[i];
array[i] = array[r];
array[r] = temp;
count++;
r--;
}
}
System.out.println(array);
}
To rotate in place both forward and backwards by any value,:
ReplyDeleteint stringRotate(int value)
{
unsigned long I,J,K;
unsigned long index0;
unsigned long temp1,temp2;
unsigned long length;
length = stringLength;
if (value < 0)
value = length - ((0 - value) % length);
if (value > length)
value = value % length;
J = 0;
index0 = J;
temp1 = stringData[J];
for (I = 0;I < length;I++)
{
K = (J + value) % length;
temp2 = stringData[K];
stringData[K] = temp1;
J = K;
temp1 = temp2;
if (J == index0)
{
J++;
index0 = J;
temp1 = stringData[J];
}
}
return 1;
}
Hi There,
ReplyDeleteGrazie! Grazie! Grazie! Your blog is indeed quite interesting around Left Rotation of String ! I agree with you on lot of points!
Since yesterday my EC2 instance in Singapore has become inaccessible to some US customers. Does anyone else have similar problems?
Please keep providing such valuable information.
Cheers,
Preethi.
Halo,
ReplyDeleteIn debt to you for making my learning on the No. 19 - Left Rotation of String area so hassle-free! I lay my faith on your writings.
I am new to AWS. They have very smart services but not easy to know what services we should use for a complex website. I required some sales person to contact me but it has been 2 weeks and no one contacted me at all. AWS Training
Follow my new blog if you interested in just tag along me in any social media platforms!
Grazie,
Ajeeth
This line of code will do the job. Rotateby is the number of times the left rotation should happen.
ReplyDeletestr.substring(rotateby%str.length())+str.substring(0,rotateby%str.length())