1. 题目链接

LeetCode题目链接

2. 思路

双指针法

对于字符串，我们定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素。一共执行了 N/2次的交换。

对于长度为 N 的待被反转的字符数组，我们可以观察反转前后下标的变化，假设反转前字符数组为 s[0] s[1] s[2] … s[N - 1]，那么反转后字符数组为 s[N - 1] s[N - 2] … s[0]。比较反转前后下标变化很容易得出 s[i] 的字符与 s[N - 1 - i] 的字符发生了交换的规律，因此我们可以得出如下双指针的解法：

• 将 left 指向字符数组首元素，right 指向字符数组尾元素。
• 当 left < right：
  1）交换 s[left] 和 s[right]；
  2） left 指针右移一位，即 left = left + 1；
  3） right 指针左移一位，即 right = right - 1。
• 当 left >= right，反转结束，返回字符数组即可。

3.代码实现

3.1 c++实现

class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {
            swap(s[i],s[j]);
        }
    }
};


//或者

class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            swap(s[left], s[right]);
        }
    }
};

3.2 c实现

void swap(char *a, char *b) {
    char t = *a;
    *a = *b, *b = t;
}

void reverseString(char *s, int sSize) {
    for (int left = 0, right = sSize - 1; left < right; ++left, --right) {
        swap(s + left, s + right);
    }
}

4.复杂度分析

• 时间复杂度：O(N)，其中 N 为字符数组的长度。一共执行了 N/2次的交换。
• 空间复杂度：O(1)。只使用了常数空间来存放若干变量。

在 Python 中，字符串是 Unicode 字符的序列，尽管 Python 支持许多用于字符串操作的函数，但它没有明确设计用于反转字符串的内置函数或方法。

>>> 'Linuxize'.reverse()

Traceback (most recent call last):
File "<input>", line 1, in <module>
AttributeError: 'str' object has no attribute 'reverse'

字符串反转不是编程中的常见操作，通常用于编码面试。

本文介绍了在 Python 中反转字符串的几种不同方法。

使用切片

了解 Python 中的索引如何工作对于执行字符串切片操作至关重要，通常，索引号用于访问字符串中的特定字符。

有两种类型的索引：正负索引

您可以n通过 的正索引号2或通过 的负索引号来访问字符-6：

>>> print('Linuxize'[2])

n

>>> print('Linuxize'[-6])

n

我们可以通过切片技术从字符串中调出一系列字符，切片是从给定字符串中提取子字符串序列的操作。

切片语法：

string[start:stop:step]

• 第一个参数指定提取开始的索引，当使用负索引时，它表示距字符串末尾的偏移量。如果省略此参数，则切片从索引 0 开始。
• 第二个参数指定结束提取的索引，结果不包括该stop元素。当使用负索引时，它表示距字符串末尾的偏移量。如果此参数被省略或大于字符串的长度，则切片到字符串的末尾。
• 第三个参数是可选的，指定切片的步骤，不使用step参数时，默认为 1。使用负值时，切片以相反的顺序获取元素。

对字符串进行切片的结果是一个包含提取元素的新字符串，并且原始字符串没有被修改。

要使用切片反转字符串，请省略startandstop参数并使用负步长增量-1.

的负步长增量-1表示切片从最后一个元素开始，到第一个元素结束，产生一个反转的字符串。

>>> print('Linuxize'[::-1])

ezixuniL

您还可以定义自定义函数并使用它来反转字符串：

def rev_str_thru_slicing(str_):
    return str_[::-1]

INPUT_STRING = "Linuxize"

if __name__ == '__main__':
    print("INPUT STRING -", INPUT_STRING)
    print("REVERSED STRING -", rev_str_thru_slicing(INPUT_STRING))

Input String - Linuxize
Reversed String using Slicing - ezixuniL

使用reversed()功能

内置reserved()函数以相反的顺序处理字符串项并返回一个反向迭代器。

在下面的示例中，使用运算符将反向迭代器的元素添加到空字符串中join()：

def rev_str_thru_join_revd(STR):
    return "".join(reversed(STR))	

INPUT_STRING = "Linuxize" 

if __name__ == '__main__':

    print("INPUT STRING -", INPUT_STRING)
    print("RESERVED STRING THROUGH JOIN & REVERSED", rev_str_thru_join_revd(INPUT_STRING))

Input String - Linuxize
Reserved String Through Join & Reserved Methods - ezixuniL

使用列表reverse()

要使用list 方法反转字符串reverse()，首先需要使用list构造函数将字符串转换为列表，然后使用该方法将列表项反转到位reverse()，最后使用该方法将列表项连接成一个字符串join()。

这是一个例子：

def rev_str_thru_list_reverse(STR):
    lst = list(STR)
    lst.reverse()
    return(''.join(lst))
 
INPUT_STRING = "Linuxize"
 
if __name__ == '__main__':
    print("Input String -", INPUT_STRING)

print("Reserved String Through List", rev_str_thru_list_reverse(INPUT_STRING))

Input String - Linuxize
Reserved String Through List Reverse Method - ezixuniL

使用递归函数

在 Python 中，递归函数是一个在满足某个条件之前调用自身的函数。

在下面的代码片段中，rev_str_thru_recursion函数调用自身，直到字符串长度大于零。每次调用时，都会对字符串进行切片，只留下第一个字符。稍后，它与切片字符连接。

def rev_str_thru_recursion(STR):
    if len(STR) == 0:
         return STR
    else:
        return rev_str_thru_recursion(STR[1:]) + STR[0]

INPUT_STRING = "Linuxize"

if __name__ == '__main__':
    print("INPUT STRING -", INPUT_STRING)

print("RESERVED STRING THROUGH RECURSION", rev_str_thru_recursion(INPUT_STRING))

对比分析

在本节中，我们将对这四种定义的方法进行简单比较，以确定它们的效率。我们将使用名为“timeit”的 Python 模块来分析性能。它提供了执行代码片段所花费的时间。“timeit”模块的“repeat”选项有助于重复代码执行一百万次。我们可以将输出理解为执行代码片段一百万次所花费的平均时间。

上表显示，Slicing 方法比 List Reverse 方法快 7 倍，比 Join & Reserved 方法快 7.5 倍，比递归方法快 83 倍。所以切片是反转字符串的最快和最好的方法。

以上结果是在相同环境下讨论的字符串反转方法的对比分析。在不同的计算环境中，数字可能会有所不同，但比例可能会保持不变。

if __name__ == "__main__":

    ## Performance Calculation

    import timeit
    from statistics import mean

    s = INPUT_STRING * 10
    repeatCount = 100

    SLICING_PERF = timeit.repeat(lambda: rev_str_thru_slicing(s), repeat=repeatCount)
    print(min(SLICING_PERF), mean(SLICING_PERF), max(SLICING_PERF), SLICING_PERF)

    J_R_PERF = timeit.repeat(lambda: rev_str_thru_join_revd(s), repeat=repeatCount)
    print(min(J_R_PERF), mean(J_R_PERF), max(J_R_PERF), J_R_PERF)

    LIST_PERF = timeit.repeat(lambda: rev_str_thru_list_reverse(s), repeat=repeatCount)
    print(min(LIST_PERF), mean(LIST_PERF), max(LIST_PERF), LIST_PERF)

    RECUR_PERF = timeit.repeat(lambda: rev_str_thru_recursion(s), repeat=repeatCount)
    print(min(RECUR_PERF), mean(RECUR_PERF), max(RECUR_PERF), RECUR_PERF)

结论

Python没有任何内置函数来反转字符串，但我们可以使用其他方法来反转字符串。回归测试分析表明，切片方法是反转字符串最快的方法。

151. 翻转字符串里的单词
     给定一个字符串，逐个翻转字符串中的每个单词。

说明：

无空格字符构成一个 单词 。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

示例 1：

输入：“the sky is blue”
输出：“blue is sky the”
示例 2：

输入：" hello world! "
输出：“world! hello”
解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：

输入：“a good example”
输出：“example good a”
解释：如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
示例 4：

输入：s = " Bob Loves Alice "
输出：“Alice Loves Bob”
示例 5：

输入：s = “Alice does not even like bob”
输出：“bob like even not does Alice”

提示：

1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ’ ’
s 中 至少存在一个 单词

思路分析：
题意已经非常明确，就是让我们反转字符串里面的单次，只不过有些条件：

1.如果字符串前面和后面有空格，全部去掉
2.中间多余的空格也去掉

很多同学可能会有一个疑惑该怎么转，如果把整个字符串反转了，那单词的顺序也不对呀，其实我们只需要将反转完成的字符串里面的单词，再次反转就行，就相当于把第一次反转完成的字符串里，在根据条件反转里面的子字符串。

本题思路：

1.去除前面、后面和中间多余的空格

在这里我们可以使用双指针法，left和right，分别指向头部和尾部，如果是空格left++ ，right–；（我们在这里假设y为空，不想重新作图）

关键问题我们如何去除中间多余的空格：
我们定义一个StringBuilder sb（因为他拼接的速度快）将去除前面和后面空格的字符串s从做到右拷贝到sb中，当s.charAt(left)不为空，我们将这个字符拷贝过去，如果为空，我们要判断上一次传入的字符是否为空，若为空跳过，不为加入到sb；

当left指针走到空格的时候判断上一个字符为k不为空，所以将空存入sb，然后left++

之后继续右走，重复以上步骤

java代码：

public StringBuilder removeSpace(String s) {
        int left = 0 , right = s.length() - 1;
        //移除开头的空格
        while (left <= right && s.charAt(left) == ' ') {
            left++;
        }
        //移除结尾的空格
        while (left <= right && s.charAt(right) == ' ') {
            right--;
        }
        StringBuilder sb = new StringBuilder();
        //移除中间多余的空格
        while (left <= right) {
            char c = s.charAt(left) ;
            if (c != ' ') {
                sb.append(c);
            }else if (sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            left++;
        }
        return sb;
    }

2.反转字符串

这个是最基础的算法了，如果有不清楚的同学，可以查看https://blog.csdn.net/qq_43413774/article/details/115082618
Java代码：

public void reverse(StringBuilder sb , int left , int right) {
        while (left < right) {
            char temp = sb.charAt(left);
            sb.setCharAt(left++ , sb.charAt(right));
            sb.setCharAt(right-- , temp);
        }

    } 

3.反转单词

就是将字符串里面被反转的单词分离开，分别进行反转

判断条件就是当遇到空格的时候分离开，并进行反转
java代码：

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);
            start = end + 1;
            end++;
        }
    }

本题思路并不难，但是就是代码逻辑性比较强，先反转还是先去空格其实都一样，甚至你都可以先反转单词，除非你闲的没事干，给自己找麻烦。

完整代码：

class Solution {
    public String reverseWords(String s) {
        //去除空格
        StringBuilder newString = removeSpace(s);
        //反转所有字符串
        reverse(newString , 0 , newString.length() - 1);
        //反转每个单次
        reverseEachWord(newString);
        
        return newString.toString();
    }

    public StringBuilder removeSpace(String s) {
        int left = 0 , right = s.length() - 1;
        //移除开头的空格
        while (left <= right && s.charAt(left) == ' ') {
            left++;
        }
        //移除结尾的空格
        while (left <= right && s.charAt(right) == ' ') {
            right--;
        }
        StringBuilder sb = new StringBuilder();
        //移除中间多余的空格
        while (left <= right) {
            char c = s.charAt(left) ;
            if (c != ' ') {
                sb.append(c);
            }else if (sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            left++;
        }
        return sb;
    }

    public void reverse(StringBuilder sb , int left , int right) {
        while (left < right) {
            char temp = sb.charAt(left);
            sb.setCharAt(left++ , sb.charAt(right));
            sb.setCharAt(right-- , temp);
        }

    } 

    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);
            start = end + 1;
            end++;
        }
    }

其实此题也可以用库函数做出来，就那么几行代码，不过不建议使用，因为大部分人不知道他们是如何实现的，就比如正则表达式，有人甚至没听过。

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

若有误，请指教!