面试热题（反转字符串中的单词）

骑猪看日落 2023-10-14 18:57 15阅读 0赞

> 给你一个字符串 `s` ，请你反转字符串中 **单词** 的顺序。
> 
> **单词** 是由非空格字符组成的字符串。`s` 中使用至少一个空格将字符串中的 **单词** 分隔开。
> 
> 返回 **单词** 顺序颠倒且 **单词** 之间用单个空格连接的结果字符串。
> 
> **注意：**输入字符串 `s`中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
> 
>     输入：s = "the sky is blue"
>     输出：
>     "blue is sky the"

![30bc213bc1bc43ba83fae65fa9e96929.png][]

看到图片中的操作，我觉得我们的第一印象应该是先用Stirng()中的方法tirm()将字符串两边的空白字符给去掉，然后再用toCharArray()方法将字符转换为char数组，然后再倒叙遍历数组填充到一个新的字符串中去，这道题就结束了，可是真的是这样么？

public String reverseWords(String s) {
          if(s.length()==0){
              return "";
          }
          //去掉两边的空格
            s=s.trim();//trim函数需要返回一个新的字符串，这里千万别忘记
          //根据“”进行分割
            String[] str=s.split(" ");
            String s1="";
            for (int i = str.length-1; i>=0; i--) {
                if(i==0){
                    s1+=str[i];
                }else{
                    s1+=str[i]+" ";
                }
                
            }
            s1=s1.trim();
            return s1;
        }

![36052ee5684045bf9410ec7be35482b9.png][]

原来这个题目中测试案例字符串中中间间隔的不一定只有一个空字符串，甚至有多个空字符串，所以我们就要对正则表达式中的规则进行一点改变

String[] str=s.split("\\s+");//匹配多个空白字符

![e1f44e9cf2b74de6af6598e2d6526e3d.png][]

过程是痛苦的但是结局确实好的

接下来给大家介绍一种比较高效的方法解决本题（双指针）

这时候有很多人就会要问了？如果遍历字符串的话，每个指针只能指向一个字符，反转的话只能使一个字符进行翻转，怎么样才可以做到对整个单词进行翻转呢？一个指针当然只可以指向一个字符了，但是两个指针就可以确定一个单词，我们可以寻找空格的位置去确定我们单词的位置

![d62afd96d03c4bb0b338b14f99eb59ea.png][]

我们做的前提得是两边没有空格的字符串，所以我们首先用String类中的trim()函数进行去除

//去掉两边的空格
      String s1=s.trim();

在操作字符串的时候，我们经常将String类型转换为StringBuilder类型进行字符串的操作

StringBuilder res=new StringBuilder();

因为我们需要进行对原字符串进行反转，干脆我们一开始就从最后面开始，这样可以省去一次翻转的时间

int i=s1.length()-1;
    int j=i;
    while(i>=0){
      ...
       }

因为我们的字符串两边没有空格，所以我们依靠中间两个单词之间的空格来确定单词的界限

while(i>=0&&s1.charAt(i)!=' '){
                    i--;
         }

![34060b7ea70a4db59354d24f66136652.png][]

因为我们要将这个字符串截取出来，将其加入到StringBuilder中，substring(start,end)函数，是一个左闭右开的取值范围

![bf92c1f2c74d46e1b6d2241aaf836bf5.png][]

res.append(s1.substring(i+1,j+1)+" ");

如果两个单词间隔许多空格的话，我们需要跳过这些空格，去寻找下一个单词的末尾字符

while(i>=0&&s1.charAt(i)==' '){
                i--;
            }

同步j指针，说明找到了一个新的单词，重复上面的步骤

j=i;

![f5dd0bbe1af84479bd87d62003f3532d.png][]

源代码如下：

public String reverseWords(String s) {
            if(s.length()==0){
                return "";
            }
            //去掉两边的空格
            String s1=s.trim();
            StringBuilder res=new StringBuilder();
            int i=s1.length()-1;
            int j=i;
         while(i>=0){
            while(i>=0&&s1.charAt(i)!=' ')i--;
            res.append(s1.substring(i+1,j+1)+" ");
            while(i>=0&&s1.charAt(i)==' ')i--;
            j=i;
            }
            return res.toString().trim();
        }

[30bc213bc1bc43ba83fae65fa9e96929.png]: https://img-blog.csdnimg.cn/30bc213bc1bc43ba83fae65fa9e96929.png
[36052ee5684045bf9410ec7be35482b9.png]: https://img-blog.csdnimg.cn/36052ee5684045bf9410ec7be35482b9.png
[e1f44e9cf2b74de6af6598e2d6526e3d.png]: https://img-blog.csdnimg.cn/e1f44e9cf2b74de6af6598e2d6526e3d.png
[d62afd96d03c4bb0b338b14f99eb59ea.png]: https://img-blog.csdnimg.cn/d62afd96d03c4bb0b338b14f99eb59ea.png
[34060b7ea70a4db59354d24f66136652.png]: https://img-blog.csdnimg.cn/34060b7ea70a4db59354d24f66136652.png
[bf92c1f2c74d46e1b6d2241aaf836bf5.png]: https://img-blog.csdnimg.cn/bf92c1f2c74d46e1b6d2241aaf836bf5.png
[f5dd0bbe1af84479bd87d62003f3532d.png]: https://img-blog.csdnimg.cn/f5dd0bbe1af84479bd87d62003f3532d.png