编程之法-字符串的旋转

描述

给定一个字符串,要求将字符串前面的若干个字符移到字符串的尾部。例如,将字符串“abcdef”的前三个字母‘a’、‘b’和‘c’移到字符串的尾部,那么原字符串将编程“defabc”。请编写一个函数实现此功能。

解法一:蛮力移位

思路

将需要移动的字符一个一个地移动到字符的最后。编写一个leftShiftOne方法,每次将一个字符移动到字符串尾部,然后调用m次这个方法,使得字符串开头的m个字符移到字符串的尾部。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
public static void main(String[] args) {
char[] s = new char[]{'a', 'b', 'c', 'd', 'e', 'f'};
leftShiftString(s, s.length, 3);
System.out.println(s);
}
//移动首部m位字符到最后
private static void leftShiftString(char[] s, int n, int m) {
while (m > 0) {
leftShiftOne(s, n);
--m;
}
}
//移动首位字符到最后
private static void leftShiftOne(char[] s, int n) {
char t = s[0];
for (int i = 1; i < n; ++i) {
s[i - 1] = s[i];
}
s[n - 1] = t;
}
}

分析

针对长度为n的字符串来说,假设需要移动m个字符到字符串的末尾,那么总共需要m*n次操作,同时设立一个变量保存第一个字符。因此时间复杂度是O(mn), 空间复杂度是O(1)

解法二:三步反转

思路

先将一个字符串分割成两个部分,然后将这两个部分的字符串分别反转,最后再对整个字符串整体反转(即三步反转),即可解决字符串旋转的问题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution2 {
public static void main(String[] args) {
char[] s = new char[]{'a', 'b', 'c', 'd', 'e', 'f'};
leftRotateString(s, s.length, 3);
System.out.println(s);
}
//字符串旋转
private static void leftRotateString(char[] s, int n, int m) {
m %= n; //若要左移动大于n位,那么与移动%n是等价的;
reverseString(s, 0, m - 1);
reverseString(s, m, n - 1);
reverseString(s, 0, n - 1);
}
//字符串反转
private static void reverseString(char[] s, int from, int to) {
while (from < to) {
char t = s[from];
s[from++] = s[to];
s[to--] = t;
}
}
}

分析

这个方法的时间复杂度为O(n),空间复杂度为O(1)

举一反三:单词反转

描述

输入一个英文句子,翻转句子中单词的顺序。要求单词内字符的顺序保持不变,句子中单词以空格隔开。为简单起见,标点符号和普通字符一样处理。例如,若输入”I am a student.”,则输出”student. a am I”.

思路

先反转每一个单词,再反转整个字符串。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution3 {
public static void main(String[] args) {
String str = "My name is luohuida!";
char[] chs = leftRotateString(str.toCharArray(), str.length());
System.out.println(chs);
}
//单词翻转
private static char[] leftRotateString(char[] s, int n) {
int i = 0;
int j = 0;
//先翻转每个单词
for (; j < n; ++j) {
if (j == n - 1 || s[j+1] == ' ') {
reverseString(s, i, j);
i = j + 2;
}
}
reverseString(s, 0, n - 1);
return s;
}
//字符串反转
private static void reverseString(char[] s, int from, int to) {
while (from < to) {
char t = s[from];
s[from++] = s[to];
s[to--] = t;
}
}
}

分析

时间复杂度O(nlogn),空间复杂度O(1)

参考文档