输入："I am a student!"
输出："student a am I"
先定义一个翻转字符串函数。
def reverse_string(s, start, end):
while start < end:
tmp = s[start]
s[start] = s[end]
s[end] = tmp
start += 1
end -= 1
return s
解决思路是对每个单词先进行翻转，然后对整个字符串进行翻转。
Step1: I am a student!
Step2: I ma a student!
Step3: I ma a student!
Step4: I ma a !tneduts
Step5: student! a am I
具体解决方案如下。
def solution(s):
s = list(s)
start_tag = 0
for i in range(s.__len__()):
if s[i] == ' ':
s = reverse_string(s, start_tag, i - 1)
start_tag = i + 1
if not start_tag == s.__len__():
s = reverse_string(s, start_tag, s.__len__() - 1)
s = reverse_string(s, 0, s.__len__() - 1)
return ''.join(s)
时间复杂度分析：
设字符串长度为n，单词数量为m，单词平均长度为l，遍历字符串为T=O(n)，翻转字符串次数为T=O(m)，翻转单词的时间复杂度为T=O(l)，在最坏情况下每个字母为一个单词，则算法时间复杂度为T=O(n^2)。
