编程之法-字符串的旋转

描述

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

解法一：蛮力移位

思路

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

代码

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)。

解法二：三步反转

思路

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

代码

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”.

思路

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

代码

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)。

参考文档

• 《编程之法》

---