字符串

字符串循环左移问题

• 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(chars, 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 该问题可作为完美洗牌算法的子算法，未完待续......