欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer面试题58 - I. 翻转单词顺序(双指针)

程序员文章站 2022-04-30 18:21:47
...

题目描述

输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。例如输入字符串"I am a student. “,则输出"student. a am I”。
剑指offer面试题58 - I. 翻转单词顺序(双指针)

思路

详见链接

代码

class Solution:
	def reverseWords(self, s:str) -> str:
		s = s.strip()   #去除首尾空格
		i = j = len(s) - 1
		res = []
		while i >= 0:
			while i >= 0 and s[i] != " ":
				i -= 1
			res.append(s[i+1:j+1])
			while s[i] == " ":
				i -= 1
			j = i
		return " ".join(res)

复杂度

时间复杂度 O(N): 其中 N 为字符串 s 的长度,线性遍历字符串。
空间复杂度 O(N)O(N) : 新建的 list(Python) 中的字符串总长度 ≤N ,占用 O(N)大小的额外空间。

相关标签: 剑指offer