今天和大家聊的问题叫做 翻转字符串里的单词 II ,我们先来看题面:https://leetcode-cn.com/problems/reverse-words-in-a-string-ii/
Given an input string , reverse the string word by word.
Example:
Input: ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
题意
给定一个字符串,逐个翻转字符串中的每个单词。
示例
示例: 输入: ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"] 输出: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"] 注意: 单词的定义是不包含空格的一系列字符 输入字符串中不会包含前置或尾随的空格 单词与单词之间永远是以单个空格隔开的 进阶:使用 O(1) 额外空间复杂度的原地解法。
解题
思路大致为:先对每个单词进行翻转,然后对句子进行翻转即可。对单词反转后,单词变得不伦不类,比如 blue 变成了 eulb,并且此时每个单词的相对位置没变。
再对句子进行一次翻转,不仅把每个单词变正常了,且每个单词的相对位置进行了翻转。
翻转的函数实现很简单,给定 str 和待翻转的索引区间即可。
class Solution { public void reverseWords(char[] str) { int i = 0; for (int j = 0; j < str.length; j++) { // aTbTc if (str[j] == ' ') { reverse(str, i, j); i = j + 1; } } reverse(str, i, str.length); // 最后一个单词末尾没有空格 System.out.println(String.valueOf(str)); reverse(str, 0, str.length); // 整体再翻转一次 } /** * 将 str 的 [i, j] 进行翻转,如 "the" 转换后变成 “eht” * 注意,[i,j] 是左闭右开 * * @param str * @param i * @param j */ private void reverse(char[] str, int i, int j) { for (int k = i; k < (i + j) / 2; k++) { char tmp = str[k]; // 位置 k 的元素 int g = j - 1 - k + i; // 位置 k 的对称位置 str[k] = str[g]; str[g] = tmp; } } }
好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。