关注Java领域相关技术 记录有趣的事情

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

US-B.Ralph
US-B.Ralph
2020-08-30

问题地址

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;
    }
};
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

16 − 12 =