Wednesday, November 2, 2011

No. 19 - Left Rotation of String


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.

6 comments:

  1. Hello

    The 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);
    }

    ReplyDelete
    Replies
    1. 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.

      Delete
    2. The solution looks more elegant, but it uses more memory to append same string. The solution in the post rotate strings in place.

      Delete
    3. String LeftRotateString(int n)
      {
      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);
      }

      Delete
  2. static void rotate(int rotate, String input)
    {
    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);
    }

    ReplyDelete
  3. To rotate in place both forward and backwards by any value,:
    int 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;
    }

    ReplyDelete