【LeetCode刷题日记】：151翻转字符串的单词（两种解法）

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺摘要本题要求翻转字符串中的单词顺序并去除首尾及单词间多余空格。核心解法分三步先去除多余空格利用双指针和StringBuilder动态判断确保单词间仅保留一个空格再反转整个字符串双指针交换字符最后逐个反转每个单词通过空格定位单词边界。另一种解法是创建新字符数组从后向前遍历原字符串提取单词并依次放入新数组天然实现顺序反转最后去掉末尾多余空格。两种方法时间复杂度均为 O(n)前者空间 O(1)后者空间 O(n)。题目背景LeetCode151 翻转字符串的单词中等给你一个字符串s请你反转字符串中单词的顺序。单词是由非空格字符组成的字符串。s中使用至少一个空格将字符串中的单词分隔开。返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。注意输入字符串s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中单词间应当仅用单个空格分隔且不包含任何额外的空格。示例 1输入s the sky is blue输出blue is sky the示例 2输入s hello world 输出world hello解释反转后的字符串中不能存在前导空格和尾随空格。示例 3输入s a good example输出example good a解释如果两个单词间有多余的空格反转后的字符串需要将单词间的空格减少到仅有一个。提示1 s.length 104s包含英文大小写字母、数字和空格 s中至少存在一个单词题目解析其实这道题目整体看上去是翻转其实还有一个重要的逻辑就是去空单词的开头不能有空格单词与单词之间就是靠一个空格来分隔的但是只有一个如果有多个就要去除。这正是题目要求的反转后的字符串中不能存在前导空格和尾随空格。如果两个单词间有多余的空格反转后的字符串需要将单词间的空格减少到仅有一个那我们来思考该怎么操作呢首先就应当先把不需要的空格都去掉否则这会影响我们之后的翻转操作因此这个操作的优先级比较高。那我们怎么去掉这些空格呢首先是首尾其实还比较简单主要的就是单词与单词之间只能有一个空格我们定义一个方法之后调用去空格。我们进行判断首位直接用while循环很轻松的就去掉两个空格了然后我们利用StringBuilder创建一个可变的字符串因为java的字符串本身是不可变的。这样我们就能对字符串进行增删改查。之后就是处理单词之间的空格了char c s.charAt(start); if (c ! || sb.charAt(sb.length() - 1) ! ) { sb.append(c); } start;情况条件说明1c ! 当前字符不是空格是字母直接加入2c 且sb最后一个字符不是空格当前是空格但上一个加入的不是空格说明这是单词间的分隔符加入一个空格这里的操作就是去掉多余的空格保证只能有一个空格。sb.charAt(sb.length() - 1)不是只找一次最后的d而是每处理一个字符时动态查看 sb 当前已经构建好的内容的最后一个字符是什么从而决定要不要添加新的空格。这是一个实时判断的过程。举例演示输入 hello world 去除首尾空格后textstart → h e l l o w o r l d ← end 0 1 2 3 4 5 6 7 8 9 10 11逐字符处理startcsb当前内容sb最后一个字符条件判断是否追加sb新内容0h(不存在)c≠空格 ✅✅h1ehhc≠空格 ✅✅he2lheec≠空格 ✅✅hel3lhellc≠空格 ✅✅hell4ohelllc≠空格 ✅✅hello5 hellooc空格 且 sb最后一个字符o≠空格 ✅✅hello 6 hello c空格 且 sb最后一个字符 ❌❌hello (不变)7whello c≠空格 ✅✅hello w8ohello wwc≠空格 ✅✅hello wo9rhello wooc≠空格 ✅✅hello wor10lhello worrc≠空格 ✅✅hello worl11dhello worllc≠空格 ✅✅hello worldprivate StringBuilder removeSpace(String s) { // System.out.println(ReverseWords.removeSpace() called with: s [ s ]); int start 0; int end s.length() - 1; while (s.charAt(start) ) start; while (s.charAt(end) ) end--; StringBuilder sb new StringBuilder(); while (start end) { char c s.charAt(start); if (c ! || sb.charAt(sb.length() - 1) ! ) { sb.append(c); } start; } // System.out.println(ReverseWords.removeSpace returned: sb [ sb ]); return sb; }去除空格之后我们要做的就是翻转整个字符串了利用双指针法逐步拆解1. 循环条件while (start end)只要左指针在右指针左边就继续交换。当两个指针相遇或交错时说明已经全部交换完毕。2. 交换三部曲java char temp sb.charAt(start); // 步骤1暂存左边的字符 sb.setCharAt(start, sb.charAt(end)); // 步骤2把右边字符放到左边位置 sb.setCharAt(end, temp); // 步骤3把暂存的左边字符放到右边位置3. 移动指针java start; // 左指针右移 end--; // 右指针左移之后就是单独的翻转单词了把单词的顺序倒过来这样就完成了我们要的翻转单词位置了我们这里定义start end是为了确定每个单词的首尾位置这要确定之后我们再调用第二步的翻转全部也就是把这一个单词的顺序翻转正常了每个单词的分界线是空格通过空格来确定。执行过程示例假设当前sb olleh world这是反转整个字符串后的结果目标是变成hello worldtext初始: o l l e h w o r l d 0 1 2 3 4 5 6 7 8 9 10 ↑ 空格位置第1轮循环处理第一个单词 olleh变量值说明start0第一个单词从索引0开始end1开始寻找单词结尾内层 whileend1,sb.charAt(1)l≠ 空格 → end2end2,sb.charAt(2)l≠ 空格 → end3end3,sb.charAt(3)e≠ 空格 → end4end4,sb.charAt(4)h≠ 空格 → end5end5,sb.charAt(5) 空格 → 循环结束找到单词范围start0, end5end指向空格java reverseString(sb, 0, 4); // 反转索引0~4 // olleh → hello题目答案class Solution { /** * 不使用Java内置方法实现 * p * 1.去除首尾以及中间多余空格 * 2.反转整个字符串 * 3.反转各个单词 */ public String reverseWords(String s) { // System.out.println(ReverseWords.reverseWords2() called with: s [ s ]); // 1.去除首尾以及中间多余空格 StringBuilder sb removeSpace(s); // 2.反转整个字符串 reverseString(sb, 0, sb.length() - 1); // 3.反转各个单词 reverseEachWord(sb); return sb.toString(); } private StringBuilder removeSpace(String s) { // System.out.println(ReverseWords.removeSpace() called with: s [ s ]); int start 0; int end s.length() - 1; while (s.charAt(start) ) start; while (s.charAt(end) ) end--; StringBuilder sb new StringBuilder(); while (start end) { char c s.charAt(start); if (c ! || sb.charAt(sb.length() - 1) ! ) { sb.append(c); } start; } // System.out.println(ReverseWords.removeSpace returned: sb [ sb ]); return sb; } /** * 反转字符串指定区间[start, end]的字符 */ public void reverseString(StringBuilder sb, int start, int end) { // System.out.println(ReverseWords.reverseString() called with: sb [ sb ], start [ start ], end [ end ]); while (start end) { char temp sb.charAt(start); sb.setCharAt(start, sb.charAt(end)); sb.setCharAt(end, temp); start; end--; } // System.out.println(ReverseWords.reverseString returned: sb [ sb ]); } private void reverseEachWord(StringBuilder sb) { int start 0; int end 1; int n sb.length(); while (start n) { while (end n sb.charAt(end) ! ) { end; } reverseString(sb, start, end - 1); start end 1; end start 1; } } }这里我们还有第二种写法代码比较简单//解法二创建新字符数组填充。时间复杂度O(n) class Solution { public String reverseWords(String s) { //源字符数组 char[] initialArr s.toCharArray(); //新字符数组 char[] newArr new char[initialArr.length1];//下面循环添加单词 最终末尾的空格不会返回 int newArrPos 0; //i来进行整体对源字符数组从后往前遍历 int i initialArr.length-1; while(i0){ while(i0 initialArr[i] ){i--;} //跳过空格 //此时i位置是边界或!空格先记录当前索引之后的while用来确定单词的首字母的位置 int right i; while(i0 initialArr[i] ! ){i--;} //指定区间单词取出(由于i为首字母的前一位所以这里1,)取出的每组末尾都带有一个空格 for (int j i1; j right; j) { newArr[newArrPos] initialArr[j]; if(j right){ newArr[newArrPos] ;//空格 } } } //若是原始字符串没有单词直接返回空字符串若是有单词返回0-末尾空格索引前范围的字符数组(转成String返回) if(newArrPos 0){ return ; }else{ return new String(newArr,0,newArrPos-1); } } }这就是典型的新开辟一个空间把旧数组循环遍历到新数组实现天然的翻转。创建新数组的时候需要多一个 位置用来放空格遍历的时候新数组的指针是从0开始原来数组的指针是从最后开始。第1轮循环提取 worldjava// 跳过空格 i15: → i14 i14: → i13 i13: d → 停止 right i 13 // 向左找单词左边界 i13: d ≠ → i12 i12: l ≠ → i11 i11: r ≠ → i10 i10: o ≠ → i9 i9: w ≠ → i8 i8: → 停止 // 单词范围 [i1, right] [9, 13] // 复制 world 空格 newArr: [w][o][r][l][d][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] 0 1 2 3 4 5 newArrPos 6第2轮循环提取 hellojava// i 当前是 8指向空格继续跳过空格 i8: → i7 i7: → i6 i6: o → 停止 right i 6 // 向左找单词左边界 i6: o ≠ → i5 i5: l ≠ → i4 i4: l ≠ → i3 i3: e ≠ → i2 i2: h ≠ → i1 i1: → 停止 // 单词范围 [i1, right] [2, 6] // 复制 hello 空格 newArr: [w][o][r][l][d][ ][h][e][l][l][o][ ][ ][ ][ ][ ][ ] 0 1 2 3 4 5 6 7 8 9 10 11 newArrPos 12设计原因newArr长度 1每个单词后加空格最后一个空格会被去掉从后往前遍历天然实现单词顺序反转单词后加空格统一处理最后再去掉末尾空格newArrPos-1去掉最后多余的那个空格优缺点分析优点思路清晰直观一次遍历完成时间复杂度 O(n)不需要多次反转操作缺点需要额外 O(n) 空间代码稍长对比两种解法特性解法一原地反转解法二新数组填充空间复杂度O(1)O(n)代码复杂度较高需要多个辅助方法较低一个方法搞定理解难度较难容易适用场景要求原地修改无空间限制结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励