LeetCode 151. 反转字符串中的单词

题目链接：LeetCode 151. 反转字符串中的单词

题意：

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

解题思路：

如果我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。
所以解题思路如下：

1. 移除多余空格
2. 将整个字符串反转
3. 将每个单词反转

另外，第二步和第三步的执行顺序是可以互换的，最终的效果是一样的。

完整代码如下(先反转单词，再反转整个字符串)：

func reverseWords(s string) string {
    k:=0  //表示去除空格后的数组的下标（因为是原地操作）
    ss:=[]byte(s)
    n:=len(ss)
    ss = append(ss,' ')//长度加 1,
    //因为在循环过程中，每次都在每个单词后面加一个空格，
//如果原字符串s，尾部没有空格，则在添加最后一个空格的时候，会报索引越界的错误。
    for i:=0;i<n;i++{
        if ss[i] != ' '{ 
            // k表示当前新数组的下标，也是一个单词的起始位置
            // t表示一个单词的终止位置
            j, t:= i,k
            for j < n && ss[j] != ' '{ //找到单个单词,起始位置是k，结束位置是 t
                ss[t] = ss[j]
                j++
                t++
            } 
            // reverse(ss[k:t])  //反转k -> t 之间的这个单词
            for a,b:=k,t-1;a<b; a,b = a+1,b-1{
                ss[a],ss[b] = ss[b],ss[a]
            }
            // 在每个单个单词后加一个空格
            ss[t]=' '
            t++
            // 更新下标
            k = t 
            i = j 
        }
    }
    //以上完成了每个单词的反转
    if k > 0{ //k > 0说明至少一个单词，因此要删除最后一个单词后添加的空格
        k--
    }
    // 删除后面多余的部分
    ss = ss[:k]
    // 反转整个链表
    m:=len(ss)
    for i,j:=0,m-1;i<j;i,j=i+1,j-1{
        ss[i],ss[j] = ss[j],ss[i]
    }
    return string(ss)
} 

完整代码如下(先反转整个字符串，再反转单词)：

func reverseWords(s string) string {
    ss:=[]byte(s)
    ss = append(ss,' ')
    n:=len(ss)
    for i,j:=0,n-1;i<j;i,j=i+1,j-1{
        ss[i],ss[j] = ss[j],ss[i]
    }
    
    k:=0  //表示去除空格后的数组的下标（因为是原地操作）
    for i:=0;i<n;i++{
        if ss[i] != ' '{ 
            // k表示当前新数组的下标，也是一个单词的起始位置
            // t表示一个单词的终止位置
            j, t:= i,k
            for j < n && ss[j] != ' '{ //找到单个单词
                ss[t] = ss[j]
                j++
                t++
            } 
            //此时单个单词的起始位置是k，终止位置是t，反转单个单词  
            for a,b:=k,t-1;a<b; a,b = a+1,b-1{
                ss[a],ss[b] = ss[b],ss[a]
            }
            // 在每个单个单词后加一个空格
            ss[t]=' '
            t++
            // 更新下标
            k = t 
            i = j 
        }

    }
    //以上完成了每个单词的反转
    if k > 0{ 
        k--
    }
    ss = ss[:k]
    return string(ss)
}