字符串

---

字符串循环左移问题

• 1 问题描述：给定一个字符串S[0…N-1],要求把S的前k个字符移到S的尾部，如把S的字符串“abcded”前面的前两个字符“a”,“b”移到字符串的尾部，得到新字符串“cdefab”，即字符串循环左移2位。
• 2 算法要求：时间复杂度为O（n）,空间复杂度为O(1)。
• 3 解题思路：三次翻转字符串解法比暴力求解复杂度小，
  假设

  X=’ab’
  Y=’cdef ‘
  X ‘ = ‘ba’
  Y ‘ = ‘ fedc ‘
  ( X ‘ Y ‘ ) ‘ = ‘ cdefab

• 4 代码

  #include<stdio.h>
   void reverseString(char *s, int from , int to)  
  {  
    while(from<to)  
    {  
    char t = s[from];  
    s[from++] = s[to];  
    s[to--] = t;  
    }  
  }  
  void leftRotateString(char*s, int n, int m)  
  {  
    m %= n;  
  reverseString(s,0,m-1);  
  reverseString(s,m,n-1);  
  reverseString(s,0,n-1);  
  }  
  int main()
  {
  char str[] = "abcdef";
  printf("The string:%s\n", str);
  leftRotateString(str, 6, 2);
  printf("After left shift:%s\n", str);
  return 0;
  }  
  

• 5 该问题可作为完美洗牌算法的子算法，未完待续……