面试经典150题——反转字符串中的单词

面试经典150题 day21

- - 题目来源
  - 我的题解
  - - 方法一双指针
    - 方法二库函数+正则匹配
    - 方法三自定义函数
    - 方法四双端队列

题目来源

力扣每日一题；题序：151

我的题解

方法一双指针

先将首尾的空格删除，然后使用两个指针从后往前遍历，end指针指向单词的末尾的下一位，start指向单词的首位的前一位。

时间复杂度：
空间复杂度：

public String reverseWords(String s) {
    s=s.trim();
    int start=s.length()-1;
    int end=s.length();
    StringBuilder sb =new StringBuilder();
    while(start>=0){
        while(start>=0&&s.charAt(start)!=' ')
            start--;
        if(start>=0){
            sb.append(s.substring(start+1,end));
            sb.append(' ');
        }else{
            sb.append(s.substring(0,end));
        }
        while(start>=0&&s.charAt(start)==' ')
            start--;
        end=start+1;
    }
    return sb.toString();
}

方法二库函数+正则匹配

利用trim、split、以及Collections.reverse和String.join几个库函数。在使用split分割函数时需要注意匹配多个连续空格

时间复杂度：O(n)
空间复杂度：O(n)

public String reverseWords(String s) {
    // 除去开头和末尾的空白字符
    s=s.trim();
    // 正则匹配连续的空白字符作为分隔符分割
    String[] strs=s.split("\\s+");
    List<String> wordL=Arrays.asList(strs);
    Collections.reverse(wordL);
    return String.join(" ",wordL);
}

方法三自定义函数

自己实现去除前后空格和内部多余空格的trimSpace函数，反转[start,end]的反转函数reverse，反转每个单词的reverseEachWord函数

时间复杂度：O(n)
空间复杂度：O(n)

public String reverseWords(String s) {
    // 除去开头和末尾的空白字符
    StringBuilder sb=trimSpace(s);
    //反转整个字符串
    reverse(sb,0,sb.length()-1);
    //翻转每个单词
    reverseEachWord(sb);
    return sb.toString();
}
public StringBuilder trimSpace(String s){
    int start=0;
    int n=s.length();
    while(start<n&&s.charAt(start)==' ')
        start++;
    int end=n-1;
    while(end>=0&&s.charAt(end)==' ')
        end--;
    StringBuilder sb=new StringBuilder();
    //删除内部多余的空格
    while(start<=end){
        char c=s.charAt(start);
        if(c!=' ')
            sb.append(c);
        else if(sb.charAt(sb.length()-1)!=' '){
            sb.append(c);
        }
        start++;
    }
    return sb;
}

public void reverse(StringBuilder sb,int start,int end){
    while(start<end){
        char s=sb.charAt(start);
        char e=sb.charAt(end);
        sb.setCharAt(start++,e);
        sb.setCharAt(end--,s);
    }
}

public void reverseEachWord(StringBuilder sb){
    int n=sb.length();
    int start=0,end=0;
    while(start<n){
        while(end<n&&sb.charAt(end)!=' ')
            end++;
        reverse(sb,start,end-1);
        while(end<n&&sb.charAt(end)==' ')
            end++;
        start=end;
        end++;
    }
}

方法四双端队列

双端队列可以在两端入队，在这里采用在头部

时间复杂度：O(n)
空间复杂度：O(n)

public String reverseWords(String s) {
    s=trimSpace(s);
    int n=s.length();
    int start=0;
    Deque<String> queue=new LinkedList<>();
    while(start<n){
        int end=start;
        while(end<n&&s.charAt(end)!=' '){
            end++;
        }
        queue.offerFirst(s.substring(start,end));
        start=end+1;
    }

    return String.join(" ",queue);
}
public String trimSpace(String s){
    int start=0;
    int n=s.length();
    while(start<n&&s.charAt(start)==' ')
        start++;
    int end=n-1;
    while(end>=0&&s.charAt(end)==' ')
        end--;
    StringBuilder sb=new StringBuilder();
    //删除内部多余的空格
    while(start<=end){
        char c=s.charAt(start);
        if(c!=' ')
            sb.append(c);
        else if(sb.charAt(sb.length()-1)!=' '){
            sb.append(c);
        }
        start++;
    }
    return sb.toString();
}