保留单词原型的字符串翻转

输入："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)。