描述
给定一个字符串,要求将字符串前面的若干个字符移到字符串的尾部。例如,将字符串“abcdef”的前三个字母‘a’、‘b’和‘c’移到字符串的尾部,那么原字符串将编程“defabc”。请编写一个函数实现此功能。
解法一:蛮力移位
思路
将需要移动的字符一个一个地移动到字符的最后。编写一个leftShiftOne方法,每次将一个字符移动到字符串尾部,然后调用m次这个方法,使得字符串开头的m个字符移到字符串的尾部。
代码
|
|
分析
针对长度为n的字符串来说,假设需要移动m个字符到字符串的末尾,那么总共需要m*n次操作,同时设立一个变量保存第一个字符。因此时间复杂度是O(mn)
, 空间复杂度是O(1)
。
解法二:三步反转
思路
先将一个字符串分割成两个部分,然后将这两个部分的字符串分别反转,最后再对整个字符串整体反转(即三步反转),即可解决字符串旋转的问题。
代码
|
|
分析
这个方法的时间复杂度为O(n)
,空间复杂度为O(1)
。
举一反三:单词反转
描述
输入一个英文句子,翻转句子中单词的顺序。要求单词内字符的顺序保持不变,句子中单词以空格隔开。为简单起见,标点符号和普通字符一样处理。例如,若输入”I am a student.”,则输出”student. a am I”.
思路
先反转每一个单词,再反转整个字符串。
代码
|
|
分析
时间复杂度O(nlogn)
,空间复杂度O(1)
。