Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

翻转字符串里的单词

Posted on Edited on In , ,
Symbols count in article: 2.2k Reading time ≈ 2 mins.

来源Leetcode第151题翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

1
2
3
输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

说明：

  • 无空格字符构成一个单词。
  • 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
  • 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

2次遍历

第一次倒序遍历将单词缓存，接着将单词翻转加入答案字符串

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
35
36
37
38
39
40
public String reverseWords(String s) {
    String ans = new String();
    String temp = new String();
    if(s.equals("") || s.equals(" "))
        return ans;
    int len = s.length();
    for(int i = len - 1 ; i >= 0 ; i--) {
        if (s.charAt(i) == ' ' && i > 1  && s.charAt(i - 1) == ' ')
            continue;
        else
        {
            if(s.charAt(i) == ' '){
                if(temp.length() == 0 ||temp.charAt(0) == ' ' )
                    continue;
                ans += reverse(temp);
                ans += ' ';
                temp = new String();
            }
            else{
                temp += s.charAt(i);
            }
        }
    }

    if(!temp.equals(" ")){
        ans += reverse(temp);
    }

    if(ans.length() > 0 && ans.charAt(ans.length() - 1) == ' ')
        return ans.substring(0,ans.length() - 1);
    return ans;
}

public static String reverse(String s) {
    char[] array = s.toCharArray();
    String reverse = "";//新建空字符串
    for (int i = array.length - 1; i >= 0; i--)
        reverse += array[i];
    return reverse;
}

库函数

trim()方法：去掉字符串两端的多余空格

1
2
3
4
5
6
7
8
9
10
11
12
public String reverseWords(String s) {
    StringBuilder ans = new StringBuilder();
    //去掉s的首尾空格 然后将字符串拆分
    String[] s1 = s.trim().split(" ");
    for(int i = s1.length - 1; i >= 0; i--){
        //空格后面的空格会变成空字符串
        if(!s1[i].equals("")) ans.append(s1[i] + " ");
    }
    //去掉最后添加上的空格
    ans = new StringBuilder(ans.toString().trim());
    return ans.toString();
}

双指针

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
public String reverseWords(String s) {
        if (null == s || s.length() == 0)
            return "";
        final char[] c = s.toCharArray();
        final int len = c.length;
        int i = len - 1;
        
        //去掉末尾的空格
        while (i >= 0 && c[i] == ' ') i--;

        int left = i + 1;
        int right = i + 1;
        StringBuffer sb = new StringBuffer(i + 1);
        
        
        for (; i >= 0; i--) {
            if (c[i] == ' ') {
                if (right != left) 
                //左不等于右是为了判断没有空格
                sb.append(c, left, right - left).append(" ");
                //加入单词
                left = i;
                right = i;
                //调整指针位置
                continue;
            }
            left = i;
            //往前找到不为空格的位置
        }
        if (right != left)
            return sb.append(c, left, right - left).toString();
        return sb.length() > 0 ? sb.substring(0, sb.length() - 1) : "";
    }