一:题目描述:
给你一个字符串 s ,请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意:输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。
二:示例与提示
示例 1:
1 2
| 输入:s = "the sky is blue" 输出:"blue is sky the"
|
示例 2:
1 2 3
| 输入:s = " hello world " 输出:"world hello" 解释:反转后的字符串中不能存在前导空格和尾随空格。
|
示例 3:
1 2 3
| 输入:s = "a good example" 输出:"example good a" 解释:如果两个单词间有多余的空格,反转后的字符串需要将单词间的空格减少到仅有一个。
|
- 提示:
1 <= s.length <= 104
s
包含英文大小写字母、数字和空格 ' '
s
中 至少存在一个 单词
三:思路
正则
先调用trim()方法去除字符串首位空格,再利用正则将单词中的多个空格替换成一个空格,然后再利用split分割成数组,调用reverse()方法反转数组,最终join(‘ ‘)将数组转换成字符串
双端队列
left指针初始在0号位置,right指针初始在s.length - 1位置,遍历字符串,将每个由空格分隔的字符串加入队列,最后在转回字符串就是翻转过后的了
重点是利用到了双端队列的特性
复杂度:时间复杂度O(n),空间复杂度O(n)
四:代码
1:排序
时间复杂度O(nlogn)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
|
var isAnagram = function(s, t) { const arr = s.split('').sort() const arr1 = t.split('').sort() var flag = 1 for(let i=0; i<Math.max(arr.length,arr1.length); i++){ if(arr[i] !== arr1[i]){ flag = 0 } } if(flag) return true else return false };
|
2:哈希表
时间复杂度O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
|
var isAnagram = function(s, t) { if(s.length !== t.length) return false
const map = new Map() for(let n of s){ if(map.has(n)){ map.set(n, map.get(n) + 1) }else{ map.set(n, 1) } }
for(let n of t){ if(map.has(n) && map.get(n) > 0){ map.set(n, map.get(n) - 1) }else{ return false } }
return true };
|