LeetCode-151. 反转字符串中的单词-Java-medium

题目链接

法一（未限定不能使用库函数）

    /**
     * 法一（未限定不能使用库函数）
     * trim()方法用来删除字符串两端的空白字符并返回一个新的字符串
     * split(" +") 是正则表达式写法，表示至少一个空格，如果有多个空格就以多个空格切分
     * join()方法返回使用指定分隔符拼接的一个字符串
     *
     * @param s
     * @return
     */
    public String reverseWords(String s) {
        String[] words = s.trim().split(" +");
        Collections.reverse(Arrays.asList(words));
        return String.join(" ", words);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

法二（禁止使用split函数，但未禁止字符串函数）

    /**
     * 法二（禁止使用split函数，但未禁止字符串函数）
     *
     * @param s
     * @return
     */
    public String reverseWords_2(String s) {
        StringBuilder sb = new StringBuilder();
        int right = s.length() - 1, left = right;
        while (left >= 0) { // 倒着遍历加到StringBuilder
            while (left >= 0 && s.charAt(left) != ' ') {
                left--;
            }
            sb.append(s.substring(left + 1, right + 1) + " ");
            while (left >= 0 && s.charAt(left) == ' ') {
                left--;
            }
            right = left;
        }
        return sb.toString().trim(); // 删除字符串末尾空格
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

法三（禁止使用split函数和字符串相关函数）

    /**
     * 去除首尾及中间多余空格
     *
     * @param s
     * @return
     */
    private StringBuilder removeSpace(String s) {
        int left = 0, right = s.length() - 1;
        while (s.charAt(left) == ' ') {  // 去除首空格
            left++;
        }
        while (s.charAt(right) == ' ') { // 去除尾空格
            right--;
        }
        StringBuilder sb = new StringBuilder();
        while (left <= right) { // 去除中间多余空格
            char c = s.charAt(left);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            left++;
        }
        return sb;
    }

    /**
     * 翻转字符串
     *
     * @param sb
     * @param left
     * @param right
     */
    private void reverseString(StringBuilder sb, int left, int right) {
        while (left < right) {
            char tmp = sb.charAt(left);
            sb.setCharAt(left++, sb.charAt(right));
            sb.setCharAt(right--, tmp);
        }
    }

    /**
     * 翻转每个单词
     *
     * @param sb
     */
    private void reverseEachWord(StringBuilder sb) {
        int left = 0, right = 1, len = sb.length();
        while (left < len) {
            while (right < len && sb.charAt(right) != ' ') { // 找到当前单词末尾
                right++;
            }
            reverseString(sb, left, right - 1); // 翻转当前单词
            left = right + 1; // 更新指针位置，去找下一个单词
            right = left + 1;
        }
    }

    /**
     * 法三（禁止使用split函数和字符串相关函数）
     * （1）去除首尾以及中间多余空格
     * （2）翻转整个字符串
     * （3）翻转各个单词
     *
     * @param s
     * @return
     */
    public String reverseWords_3(String s) {
        StringBuilder sb = removeSpace(s);
        reverseString(sb, 0, sb.length() - 1);
        reverseEachWord(sb);
        return sb.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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

本地测试

        /**
         * 151. 反转字符串中的单词
         */
        lay.showTitle(151);
        Solution151 sol151 = new Solution151();
        String s151_1 = "a good   example";
        String s151_2 = "a good   example";
        String s151_3 = "a good   example";
        System.out.println(s151_1);
        System.out.println(sol151.reverseWords(s151_1));
        System.out.println(sol151.reverseWords_2(s151_2));
        System.out.println(sol151.reverseWords_3(s151_3));
1
2
3
4
5
6
7
8
9
10
11
12