【算法】反转字符串

Algorithm 阅读量

前言

研究算法能提高我们的编程功底，更好地编写出高效稳健的代码。今天，我们研究的是 —— 反转字符串。

1
2
3
//输入一个字符串，输出它的倒序字符串
input:  Hello
output: olleH

解法

反转字符串，确实没什么难度，但是我无意间搜索了一下，才发现这么一个看似简单的反转算法实现起来真可谓花样繁多。这里我们尽可能分别总结介绍一下。

1、使用字符数组倒序输出

最常规的解法，也是最容易想到的一种方法就是使用字符数组倒序输出。

具体思路是：倒序遍历字符串字符循环给char数组赋值

1
2
3
4
5
6
7
8
9
public static String strReverseWithArray(String string) {
    if (string == null || string.length() == 0) return string;
    
    char[] array = new char[string.length()];
    for(int i = 0; i < string.length(); i++){
        array[i] = string.charAt(string.length() - i - 1);
    }
    return new String(array);
}

优化：

分析上面这种解法，循环遍历时，我们其实不需要循环这么多次。每次循环的时候，我们应该直接给前、后位置（第一个和最后一个，第二个和倒数第二个）交换。也就是说我们不必对这个字符数组进行完全遍历，通常情况下我们会只遍历一半同时交换中轴前后两个元素就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static String strReverseWithArray(String string) {
    if (string == null || string.length() == 0) return string;

    char[] array = string.toCharArray();
    //注意这里中间的位置计算
    for(int i = 0; i < Math.ceil(string.length() / 2.0f); i++){
        int j = string.length() - i - 1;
        if(i != j){		//交换元素
            char temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    return new String(array);
}

2、使用StringBuilder

StringBuilder可以帮助我们创建字符串，所以也可以使用StringBuilder替代字符数组存储，具体思路是:

逆序遍历字符串中的字符，并将它依次添加到StringBuilder中

1
2
3
4
5
6
7
8
9
public static String strReverseWithStringBuilder(String string) {
    if (string == null || string.length() == 0) return string;

    StringBuilder sb = new StringBuilder();
    for(int i = string.length() - 1; i >= 0; i--){
        sb.append(string.charAt(i));
    }
    return sb.toString();
}

以上这几种方法按算法角度来说，其实可以归结为一类。然而下面的几种算法就完全不是同一类型的了。
比如使用栈、使用异或运算。

3、使用StringBuilder.reverse()方法

1
new StringBuilder(hi).reverse().toString()

StringBuilder中提供了reverse()方法来实现字符串反转，我们可以直接调用

1
2
3
4
5
public static String strReverseWithRecursive(String string) {
    if (string == null || string.length() == 0) return string;
   
    return new StringBuilder(string).reverse().toString();
}

Or, for versions earlier than JDK 1.5, use java.util.StringBuffer instead of StringBuilder — they have the same API. Thanks commentators for pointing out that StringBuilder is preferred nowadays.

对于JDK 1.5之前的版本可以使用StringBuffer替代StringBuilder，这两个的API都一样。

4、使用栈

我们都知道，栈有“后进先出(LIFO)”的特点。这一特点刚好用于反转字符串。具体思路是:

  • 将字符串转换为char数组
  • 将char数组中的字符依次压入栈中
  • 将栈中的字符依次弹出赋值给char数组
1
2
3
4
5
6
7
8
9
10
11
12
13
public static String strReverseWithStack(String string) {
    if (string == null || string.length() == 0) return string;

    char[] array = string.toCharArray();        
    Stack<Character> stack = new Stack<Character>();
    for(Character c : array){
        stack.push(c);		//压栈
    }
    for(int i = 0; i < string.length(); i++){
        array[i] = stack.pop();
    }
    return new String(array);	//出栈
}

两次循环和栈的开销无疑使这种方法成为目前为止开销最大的方法。但使用栈这个数据结构的想法还是非常有价值的。

5、使用异或运算

计算机的数据流本质上都是0，1二进制数据。字符串也是一样。而二进制数据的处理往往是通过位运算来实现的。位操作有：与，或，非，异或。

对位运算有过了解的应该知道，使用异或操作能实现交换两个变量的值而不引入第三个变量。

实现原理:

  • 首先介绍异或操作
1
2
3
4
5
6
7
异或操作: 当两两数值相同为否，而数值不同为真。写作A^B

A  B  A^B
0  0   0
0  1   1
1  0   1
0  1   0
  • 使用异或操作交换数值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
两个数异或的结果再与其中一个数异或的结果是另外一个数

这涉及到了离散数学中的异或的性质:
1.交换律:A^B=B^A
2.结合律: A^(B^C)=(A^B)^C
3.恒等律:X^0=0
4.归零律:X^X=0
5.自反：A^B^B = A^0=A

根据以上性质:

A=A^B
B=A^B
A=A^B

通过以上三步，能实现在程序中交换两个变量的数值的目标。
  • 使用异或操作交换字符值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
before:"Hello"
after: "olleH"

index: 0   1   2   3   4
char : H   e   l   l   o
ASCII: 72  101 108 108 111

以第0个字符和第4个字符交换为例:

交换前:
array[0]=1001000
array[4]=1101111

交换:
array[0]=array[0]^array[4]=0100111
array[4]=array[4]^array[0]=1001000
array[0]=array[0]^array[4]=1101111

交换后:
array[0]=1101111--->111-->o
array[4]=1001000--->72--->H

使用这种交换方法，每次循环的时候，我们直接给中轴前、后位置元素（第一个和最后一个，第二个和倒数第二个）交换。这样我们也只遍历一半就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
public static String strReverseWithArray(String string) {
    if (string == null || string.length() == 0) return string;

    char[] array = string.toCharArray();
    for(int i = 0, j = string.length() - 1; i < j; i++, j--){
    	//异或运算交换元素
        array[i] ^= array[j];
        array[j] ^= array[i];
        array[i] ^= array[j];
    }
    return new String(array);
}

6、使用递归

当我们反转字符串的时候，脑海里想的就是从首尾两端依次交换直到到达中间位置。当我们在反转某个字符时，剩下的字符串也是一个反转字符串的过程。这样，我们就能用递归的方法来实现反转字符串的目的。

具体思路是:

  • 找出递归结束的临界条件
  • 对针对于临界条件的不同的值做出不同的处理

编码实现：

1
2
3
4
5
6
7
8
9
10
public static String strReverseWithRecursive(String string) {
    if (string == null || string.length() == 0) return string;

    if(string.length() == 1){
    	return string;
    }else{
        //当前str的反转 = 将第一个元素之后的subString反转 + 第一个元素
    	return strReverseWithRecursive(string.substring(1)) + string.charAt(0);
    }
}

引申问题

反转一个字符串有这么多方法，那么如何把一个字符串反转，而单词不翻转呢？

题目：写一个函数，将字符串反转，反转方式如下：

1
2
3
//输入一个字符串，输出它的倒序字符串，单词不翻转
input:  "I am a student"
output: "student a am I"

解决

我们可以仿照上面的字符串完全反转方法。

比如使用栈，可以把单词入栈，而不是字符，然后出栈，就是想要的效果了。或者也使用StringBuilder倒序存储，如下：

1
2
3
4
5
6
7
8
9
public static String reverse(String word){
	String[] arr = word.split("\\W+");
	StringBuffer sb = new StringBuffer();
	int len = arr.length;
	for(int i = len-1; i >= 0; i--){
		sb.append(arr[i]).append(" ");
	}
	return sb.toString();
}

还有一种思路是：先把整个字符串完全反转，再将字符串分割为单词，每个单词再单独反转回来。这种办法也没什么问题，大家可以参考一下。

参考资料

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2019 iTimeTraveler All Rights Reserved.

访客数 : | 访问量 :