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”.
Use classic algorithm: reverse twice to 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.
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;
}
Read full article from Coding Interview Questions: No. 19 - Left Rotation of String