LeetCode-557. 反转字符串中的单词 III

问题地址

LeetCode每日一题/2020-08-30

LeetCode557. 反转字符串中的单词 III

问题描述

规则

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例1

输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

提示

• 在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

解析

解题思路

方案一：栈

利用栈先进后出的特点：遍历字符串s，非空格字符入栈，遇到空格时出栈。

方案二：

使用空格切分字符串，遍历字符串数组，反转每个字符串。

复杂度分析

1. 时间复杂度，O(n)。N为字符串长度。

2. 空间复杂度，O(n)。需要一个数组存放切分后的字符串数组。

定位问题

数据操作分析

• 单词切分
• 单词反转

编码实现

/**
 * Leetcode557
 * 栈
 */
public class LeetCode557_ReverseWordsInAString {
    public String reverseWords(String s) {
        StringBuffer sb = new StringBuffer();
        Stack<String> storage = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            String tmp = s.substring(i, i + 1);
            if (s.substring(i, i + 1).equals(" ")) {
                sb.append(takeStr(storage)).append(" ");
                continue;
            }
            storage.push(tmp);
        }
        if (!storage.isEmpty()) sb.append(takeStr(storage));
        return sb.toString();
    }

    private String takeStr(Stack<String> storage) {
        if (storage.isEmpty()) return "";
        StringBuffer sb = new StringBuffer();
        while (!storage.isEmpty()) {
            sb.append(storage.pop());
        }
        return sb.toString();
    }

}

/**
 * Leetcode557
 * 切分字符串，遍历字符串数组
 */
public class LeetCode557_ReverseWordsInAString {
    public String reverseWords(String s) {
        String[] strings = s.split(" ");
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < strings.length; i++) {
            sb.append(new StringBuffer(strings[i]).reverse());
            if (i < strings.length-1) sb.append(" ");
        }
        return sb.toString();
    }
}

官方解法

使用额外空间

思路：

• 开辟一个新字符串。然后从头到尾遍历原字符串，直到找到空格为止，此时找到了一个单词，并能得到单词的起止位置。随后，根据单词的起止位置，可以将该单词逆序放到新字符串当中。如此循环多次，直到遍历完原字符串，就能得到翻转后的结果。

复杂度分析：

• 时间复杂度：O(N)，其中 N 为字符串的长度。原字符串中的每个字符都会在 O(1) 的时间内放入新字符串中。

• 空间复杂度：O(N)。我们开辟了与原字符串等大的空间。

class Solution {
    public String reverseWords(String s) {
        StringBuffer ret = new StringBuffer();
        int length = s.length();
        int i = 0;
        while (i < length) {
            int start = i;
            while (i < length && s.charAt(i) != ' ') {
                i++;
            }
            for (int p = start; p < i; p++) {
                ret.append(s.charAt(start + i - 1 - p));
            }
            while (i < length && s.charAt(i) == ' ') {
                i++;
                ret.append(' ');
            }
        }
        return ret.toString();
    }
}

原地解法

思路

• 此题也可以直接在原字符串上进行操作，避免额外的空间开销。当找到一个单词的时候，我们交换字符串第一个字符与倒数第一个字符，随后交换第二个字符与倒数第二个字符…… 如此反复，就可以在原空间上翻转单词。

• 需要注意的是，原地算法在某些语言（比如 Java，JavaScript）中不适用，因为在这些语言中 String 类型是一个不可变的类型。

复杂度分析：

• 时间复杂度：O(O(N)。字符串中的每个字符要么在 O(1) 的时间内被交换到相应的位置，要么因为是空格而保持不动。

• 空间复杂度：O(1)。因为不需要开辟额外的数组。

class Solution {
public: 
    string reverseWords(string s) {
        int length = s.length();
        int i = 0;
        while (i < length) {
            int start = i;
            while (i < length && s[i] != ' ') {
                i++;
            }

            int left = start, right = i - 1;
            while (left < right) {
                swap(s[left], s[right]);
                left++;
                right--;
            }
            while (i < length && s[i] == ' ') {
                i++;
            }
        }
        return s;
    }
};