反转句子中的单词

题目描述

给定一个句子（字符数组），请在不改变单词内部字母顺序的前提下，将单词的顺序反转。所有操作必须原地进行。

示例

字符串 "Hello World" 应被反转为 "World Hello"。

以下是另一个反转句子中单词的例子：

输入样例

1"Hello world."

期望输出

1"world. Hello"

注意：单词内部字母的顺序不会被反转。

自行尝试

多标签代码

C++

1#include <iostream>
2#include <string>
3#include <string.h>
4#include <vector>
5
6using namespace std;
7
8void StrRev(char* str, char* start, char* end) {
9	// 返回如果字符串为空或长度小于2
10	if (str == nullptr) {
11		return;
12	}
13
14	// 从两端开始交换字符，向字符串中心移动
15	while (start < end) {
16		if (start != nullptr && end != nullptr){
17			char temp = *start;
18			*start = *end;
19			*end = temp;
20		}
21		start++;
22		end--;
23	}
24}
25
26void ReverseWords(char* sentence) {
27	// 这里 sentence 是以 '\0' 结尾的空终止字符串。
28	if (sentence == nullptr) {
29		return;
30	}
31
32	// 为了反转字符串中的所有单词，我们首先反转整个字符串。
33	// 此时所有单词都处于目标位置，但顺序相反："Hello World" -> "dlroW olleH"。
34	int len = strlen(sentence);
35	char* start = sentence;
36	char * end = sentence + len - 1;
37	StrRev(sentence, start, end);
38
39	// 现在，遍历字符串并逐个反转每个单词。
40	// "dlroW olleH" -> "World Hello"
41
42	while (true) {
43		// 跳过空格，找到单词的起始位置。
44		while (start && *start == ' ') {
45			start++;
46		}
47
48		if (start == nullptr || *start == '\0') {
49			break;
50		}
51
52		// 找到单词的结束位置。
53		end = start + 1;
54		while (end && *end != '\0' && *end != ' ') {
55			end++;
56		}
57
58		// 反转该单词。
59		if (end != nullptr){
60			StrRev(sentence, start, end - 1);
61		}
62
63		start = end;
64	}
65}
66
67int main() {
68	string str_to_reverse1 = "Hello World!";
69	cout << "1.    Actual string:   " <<	str_to_reverse1 << endl;
70	char* reversed1 = const_cast<char*>(str_to_reverse1.c_str());
71	ReverseWords(reversed1);
72	string reversed1_str(reversed1);
73	cout << "      Reversed string: " << reversed1_str << endl;
74
75	cout << "\n-----------------------------------------------------------------------------------------------------\n" << endl;
76
77	string str_to_reverse2 = "The quick brown fox jumped over the lazy dog.";
78	cout << "2.    Actual string:   " <<	str_to_reverse2 << endl;
79	char* reversed2 = const_cast<char*>(str_to_reverse2.c_str());
80	ReverseWords(reversed2);
81	string reversed2_str(reversed2);
82	cout << "      Reversed string: " << reversed2_str << endl;
83
84	cout << "\n-----------------------------------------------------------------------------------------------------\n" << endl;
85	
86}

Java

1// 导入所需函数
2import java.util.*;
3
4class ReverseWords {
5	// Java 中不使用空终止字符串
6	public static void strRev(char[] str, int start, int end) {
7		// 如果字符串为空或长度小于1，则返回
8		if (str == null || str.length < 1) {
9			return;
10		}
11
12		// 从两端开始交换字符，向字符串中心移动
13		while (start < end) {
14			char temp = str[start];
15			str[start] = str[end];
16			str[end] = temp;
17			start++;
18			end--;
19		}
20	}
21
22	public static String reverseWords(char[] sentence) {
23		// 这里 sentence 是以 '\0' 结尾的空终止字符串？
24		if (sentence == null || sentence.length == 0) {
25			return "String is empty";
26		}
27
28		// 为了反转字符串中的所有单词，我们首先反转整个字符串。
29		// 此时所有单词都处于目标位置，但顺序相反："Hello World" -> "dlroW olleH"。
30		int strLen = sentence.length;
31		strRev(sentence, 0, strLen - 1);
32		
33		// 现在，遍历句子并逐个反转每个单词。
34		// "dlroW olleH" -> "World Hello"
35		int start = 0;
36		int end = 0;
37
38		while (true) {
39			if (start >= strLen - 1) {
40				break;
41			}
42
43			// 跳过空格，找到单词的起始位置。
44			while (sentence[start] == ' ') {
45				start++;
46			}
47
48			// 找到单词的结束位置。
49			end = start + 1;
50			while (end < strLen && sentence[end] != ' ') {
51				end++;
52			}
53
54			// 反转单词。
55			strRev(sentence, start, end - 1);
56			start = end;
57		}
58
59		return String.valueOf(sentence);
60	}
61
62	public static void main(String[] args) {
63		String stringToReverse1 = "Hello World!";
64		System.out.println("1.    Actual string:   " + stringToReverse1);
65		char[] stringChar = stringToReverse1.toCharArray();
66		
67		System.out.println("      Reversed string: " + reverseWords(stringChar));
68		System.out.println(
69				"\n-----------------------------------------------------------------------------------------------------\n");
70		String stringToReverse2 = "The quick brown fox jumped over the lazy dog.";
71		System.out.println("2.    Actual string:   " + stringToReverse2);
72		stringChar = stringToReverse2.toCharArray();
73		
74		System.out.println("      Reversed string: " + reverseWords(stringChar));
75		System.out.println(
76				"\n-----------------------------------------------------------------------------------------------------\n");
77	}
78}

Python

1def str_rev(_str, start, end):
2    # 如果字符串为空或长度小于2，则返回
3    if not _str or len(_str) < 2:
4        return
5
6    # 从两端开始交换字符，向字符串中心移动
7    while start < end:
8        temp = _str[start]
9        _str[start] = _str[end]
10        _str[end] = temp
11
12        start += 1
13        end -= 1
14
15
16def reverse_words(sentence):
17
18    # 这里 sentence 是以 '\0' 结尾的空终止字符串。
19    if not sentence:
20        return "String is empty"
21
22    # 为了反转字符串中的所有单词，我们首先反转整个字符串。
23    # 此时所有单词都处于目标位置，但顺序相反："Hello World" -> "dlroW olleH"。
24    str_len = len(sentence)
25    str_rev(sentence, 0, str_len - 1)
26
27    # 现在，遍历句子并逐个反转每个单词。
28    # "dlroW olleH" -> "World Hello"
29    start = 0
30    end = 0
31
32    while True:
33
34        # 跳过空格，找到单词的起始位置。
35        while start < len(sentence) and sentence[start] == ' ':
36            start += 1
37
38        if start == str_len:
39            break
40
41        # 找到单词的结束位置。
42        end = start + 1
43        while end < str_len and sentence[end] != ' ':
44            end += 1
45
46        # 反转单词。
47        str_rev(sentence, start, end - 1)
48        start = end
49
50def main():
51    string_to_reverse1 = list("Hello World!")
52    print("1.    Actual string:   " + "".join(string_to_reverse1))
53    reverse_words(string_to_reverse1)
54    print("      Reversed string: " + "".join(string_to_reverse1))
55    print("-----------------------------------------------------------------------------------------------------")
56    string_to_reverse2 = list("The quick brown fox jumped over the lazy dog.")
57    print("2.    Actual string:   " + "".join(string_to_reverse2))
58    reverse_words(string_to_reverse2)
59    print("      Reversed string: " + ("".join(string_to_reverse2)))
60    print("-----------------------------------------------------------------------------------------------------")
61
62
63if __name__ == '__main__':
64    main()

JS

1let strRev = function(str, start, end) {
2  // 如果字符串为空或长度小于2，则返回
3  if (!str || str.length < 2) {
4    return;
5  }
6  // 从两端开始交换字符，向字符串中心移动
7  while (start < end) {
8    let temp = str[start];
9    str = str.substr(0, start) + str[end] + str.substr(start + str[end].length);
10    str = str.substr(0, end) + temp + str.substr(end + temp.length);
11
12    start++;
13    end--;
14  }
15
16  return str;
17};
18
19let reverseWords = function(sentence) {
20
21  // 这里 sentence 是以 '\0' 结尾的空终止字符串。
22  if (!sentence || sentence.length === 0) {
23    return "String is empty";
24  }
25
26  // 为了反转字符串中的所有单词，我们首先反转整个字符串。
27  // 此时所有单词都处于目标位置，但顺序相反："Hello World" -> "dlroW olleH"。
28  let strLen = sentence.length;
29  sentence = strRev(sentence, 0, strLen - 1);
30
31  // 现在，遍历句子并逐个反转每个单词。
32  // "dlroW olleH" -> "World Hello"
33  let start = 0;
34  let end = 0;
35  
36  while (true) {
37    // 跳过空格，找到单词的起始位置。
38    while (sentence[start] === ' ') {
39      start++;
40    }
41    if (start >= sentence.length) {
42      break;
43    }
44
45    // 找到单词的结束位置。
46    end = start + 1;
47    while (end < sentence.length && sentence[end] != ' ') {
48      end++;
49    }
50
51    // 反转单词。
52    sentence = strRev(sentence, start, end - 1);
53
54    start = end;
55  }
56  return sentence;
57};
58
59let stringToReverse1 = "Hello World!";
60let stringToReverseResult1 = reverseWords(stringToReverse1);
61console.log("1.    Actual string:   " + stringToReverse1);
62console.log("      Reversed string: " + stringToReverseResult1);
63console.log("\n-----------------------------------------------------------------------------------------------------\n" );
64let stringToReverse2 = "The quick brown fox jumped over the lazy dog.";
65let stringToReverseResult2 = reverseWords(stringToReverse2);
66console.log("2.    Actual string:   " + stringToReverse2);
67console.log("      Reversed string: " + stringToReverseResult2);
68console.log("\n-----------------------------------------------------------------------------------------------------\n" );

Ruby

1def str_rev(str, start, last)
2	# 如果字符串为空或长度小于2，则返回
3  	return if str == nil || str.length < 2
4  
5	# 从两端开始交换字符，向字符串中心移动
6  	while start < last do
7		temp = str[start]
8		str[start] = str[last]
9		str[last] = temp
10
11		start += 1
12		last -= 1
13	end
14end
15
16
17def reverse_words(sentence)
18 	# 这里 sentence 是以 '\0' 结尾的空终止字符串。
19	return "String is empty" if sentence == nil || sentence.length == 0
20
21	# 为了反转字符串中的所有单词，我们首先反转整个字符串。
22	# 此时所有单词都处于目标位置，但顺序相反："Hello World" -> "dlroW olleH"。
23	str_len = sentence.length
24	str_rev(sentence, 0, str_len - 1)
25
26	# 现在，遍历句子并逐个反转每个单词。
27	# "dlroW olleH" -> "World Hello"
28	start = last = 0
29
30	while true do
31		# 跳过空格，找到单词的起始位置。
32		start += 1 while start < sentence.length && sentence[start] == ' '
33
34		break if start == str_len
35
36		# 找到单词的结束位置。
37		last = start + 1
38		last += 1 while last < str_len && sentence[last] != ' '
39
40		# 反转单词。
41		str_rev(sentence, start, last - 1)
42		start = last
43	end
44end
45
46# 主函数
47inputs = ["Hello World!", "The quick brown fox jumped over the lazy dog."]
48
49inputs.length.times do |i|
50	puts (i + 1).to_s + ".    Actual string:   " + inputs[i]
51	reverse_words(inputs[i])
52	puts "      Reversed string: " + inputs[i]
53	puts "-----------------------------------------------------------------------------------------------------\n"
54end

Go

1package main
2import (
3	"fmt"
4)
5// StrRev 是一个辅助函数
6func StrRev(str string, start int, end int) string{
7	// 如果长度小于2，则直接返回
8	if  len(str) < 2 {
9		return str
10	}
11	/*
12		由于 Go 中字符串是不可变的，
13		因此我们将其转换为 rune 切片进行反转，
14		然后再转回字符串并返回。
15	*/
16	// 将字符串转换为 rune 切片
17	strOut := []rune(str) 
18	// 从两端开始交换字符，向字符串中心移动
19	
20	for start < end {
21		strOut[start],  strOut[end] = strOut[end], strOut[start]
22		start += 1
23		end -= 1
24	}
25	return string(strOut)
26}
27/* ReverseWords 是我们的挑战函数，用于反转给定句子中的单词 */
28func ReverseWords(sentence string) string {
29	if len(sentence) == 0 {
30		return "String is empty"
31	}
32
33	strLen := len(sentence)
34	// 为了反转字符串中的所有单词，我们首先反转整个字符串。
35	// 此时所有单词都处于目标位置，但顺序相反："Hello World" -> "dlroW olleH"。
36
37	s := StrRev(sentence, 0, strLen-1)
38
39	// 现在，遍历句子并逐个反转每个单词。
40	// "dlroW olleH" -> "World Hello"
41	start, end := 0, 0
42	for {
43		// 跳过空格，找到单词的起始位置。
44		for start < len(s) && s[start] == ' ' {
45			start += 1
46		}
47		if start == strLen {
48			break
49		}
50		// 找到单词的结束位置。
51		end = start + 1
52		for end < strLen && s[end] != ' ' {
53			end += 1
54		}
55		// 反转单词。
56		s = StrRev(s, start, end-1)
57		start = end
58	}
59
60	return s;
61}
62
63
64func main() {
65
66	stringToReverse := []string {"Hello World!", "The quick brown fox jumped over the lazy dog."}
67
68	for i, str := range stringToReverse{
69		fmt.Printf("%d.    Actual string:   %s\n", i + 1, str)
70		ReverseWords(str)
71		fmt.Printf("      Reversed string: %s", ReverseWords(str))
72		fmt.Print(
73			"\n-----------------------------------------------------------------------------------------------------\n",
74		)
75	}
76}

时间复杂度

此解决方案的时间复杂度为线性，$O(n)$。

空间复杂度

此解决方案的空间复杂度为常数，$O(1)$。

注意：该解法在原地反转每个单词，无需额外空间。