• 1. 反转字符串
• 2. 反转字符串||
• 3. 翻转字符串中的单词
  • 思路一：使用库函数
  • 思路二：自定义函数
• 4. 找出字符串中第一个匹配项的下标
• 5. 重复的子字符串

1. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须**原地 (opens new window)修改输入数组**、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]

输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]

输出：["h","a","n","n","a","H"]

提示：

• 1 <= s.length <= 105
• s[i] 都是 ASCII (opens new window) 码表中的可打印字符

解题思路如下：力扣链接 (opens new window)

这道题可以使用双指针法简单有效地解决。核心思路是将两端的字符逐个交换，直到两个指针相遇或者交错。

1. 初始化指针：设置两个指针，left 指向数组的起始位置，right 指向数组的结束位置。
2. 遍历和交换：当 left < right 时，交换 s[left] 和 s[right] 的值，然后移动指针：left 向右移动一位，right 向左移动一位。
3. 终止条件：当 left >= right 时，停止循环。
4. 原地修改：整个过程中不需要使用额外的空间，直接在输入数组上操作即可。

• 时间复杂度是 O(n/2)，即 O(n)，因为每对字符只需要交换一次。

双指针解题代码如下

class Solution {
    public void reverseString(char[] s) {
        int left = 0; // 初始化左指针
        int right = s.length - 1; // 初始化右指针

        while (left < right) {
            // 交换左右指针所指的字符
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;

            // 移动指针
            left++;
            right--;
        }
    }
}

2. 反转字符串||

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2

输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2

输出："bacd"

提示：

• 1 <= s.length <= 104
• s 仅由小写英文组成
• 1 <= k <= 104

解题思路如下：力扣链接 (opens new window)

为了解决这个问题，我们可以遍历字符串，并按照题目的要求在每个 2k 长度的区间内对前 k 个字符进行反转。我们可以分三种情况讨论：

1. 如果剩余字符少于 k 个，则将这些字符全部反转。
2. 如果剩余字符少于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
3. 对于完整的 2k 字符区间，反转区间的前 k 个字符。

• 时间复杂度是外部循环次数乘以每次循环中的操作复杂度，即 O((n / (2k)) * k)，简化后可得到 O(n)。

双指针解题代码如下

class Solution {
    public String reverseStr(String s, int k) {
        // 将输入字符串转换为字符数组，便于操作
        char[] arr = s.toCharArray();
        int n = arr.length;

        // 遍历字符串，每次跳过 2k 个字符
        for (int start = 0; start < n; start += 2 * k) {
            // 计算每个区间的结束位置，取 start+k-1 和 字符串长度-1 中的较小值
            // 如果 start + k - 1 大于 n - 1，说明已经到末尾了
            // 此时剩余字符少于k个，只需要反转剩余字符即可，也就是反转到末尾位置
            int end = Math.min(start + k - 1, n - 1);

            // 反转从 start 到 end 的字符
            reverse(arr, start, end);
        }

        // 将处理后的字符数组转换为字符串并返回
        return new String(arr);
    }

    // 反转字符数组的指定区间 [start, end]
    private void reverse(char[] arr, int start, int end) {
        // 使用两个指针从两端向中间遍历，交换两端的字符
        while (start < end) {
            char temp = arr[start];
            arr[start++] = arr[end];
            arr[end--] = temp;
        }
    }
}

3. 翻转字符串中的单词

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

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"

输出："blue is sky the"

示例 2：

输入：s = " hello world "

输出："world hello"

解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good example"

输出："example good a"

解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

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

解题思路如下：力扣链接 (opens new window)

思路一：使用库函数

java对字符串提供了 split（拆分），reverse（翻转）和 join（连接）等方法，因此我们可以简单的调用内置的 API 完成操作：

1. 使用 split 将字符串按空格分割成字符串数组；
2. 使用 reverse 将字符串数组进行反转；
3. 使用 join 方法将字符串数组拼成一个字符串。

• 时间复杂度主要取决于 split 和 join 方法，大致为 O(n)，其中 n 是字符串 s 的长度。
• 空间复杂度也是 O(n)，用于存储分割后的单词数组

class Solution {
    public String reverseWords(String s) {
        // 使用 split 方法按空格分割字符串，得到单词数组
        // "\\s+" 正则表达式表示匹配任意多个空格
        String[] words = s.trim().split("\\s+");

        // 使用 Collections 的 reverse 方法反转数组中的单词顺序
        Collections.reverse(Arrays.asList(words));

        // 使用 String 的 join 方法将单词数组连接为一个字符串
        // 单词之间用一个空格隔开
        return String.join(" ", words);
    }
}

思路二：自定义函数

这个解法涉及到三个步骤：去除多余空格、整体反转字符串、反转各个单词。

举个例子，源字符串为："the sky is blue "

• 移除多余空格 : "the sky is blue"
• 字符串反转："eulb si yks eht"
• 单词反转："blue is sky the"

1. 去除多余空格：
   • 创建一个 StringBuilder 来存储处理后的字符串。
   • 移除字符串前后的空格。
   • 移除字符串中间多余的空格，即如果当前字符不是空格或者当前字符是空格但前一个字符不是空格时，将其添加到 StringBuilder 中。
2. 反转整个字符串：
   • 使用双指针法对 StringBuilder 进行反转操作。
   • 一个指针 start 从字符串开始处，另一个指针 end 从字符串末尾开始。
   • 交换 start 和 end 指向的字符，并向中间移动，直到 start >= end。
3. 反转各个单词：
   • 再次使用双指针遍历 StringBuilder。
   • start 指向单词的开始，end 指向单词的结束。
   • 对每个单词使用之前的反转方法。

• 时间复杂度是 O(n)，其中 n 是字符串 s 的长度。

• 空间复杂度也是 O(n)，主要是存储处理后的字符串所使用的空间

class Solution {
    public String reverseWords(String s) {
        // 去除首尾以及中间多余空格
        StringBuilder sb = removeSpace(s);
        // 反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        // 反转各个单词
        reverseEachWord(sb);
        return sb.toString();
    }

    private StringBuilder removeSpace(String s) {
        int start = 0;
        int end = s.length() - 1;
        // 去除字符串前后空格
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        // 去除字符串中间多余的空格
        while (start <= end) {
            char c = s.charAt(start);
	    // 如果当前c不是空格，直接放进新的sb字符串里面
	    // 如果当前c是空格，检查当前sb字符串的最后一个是不是空格，不是空格才添加当前字符c
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        return sb;
    }

    public void reverseString(StringBuilder sb, int start, int end) {
        // 使用双指针法反转字符串
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
    }

    private void reverseEachWord(StringBuilder sb) {
        int start = 0, end = 1, n = sb.length();
        // 遍历字符串，反转每个单词
        while (start < n) {
            // 寻找单词的结束位置
            while (end < n && sb.charAt(end) != ' ') {
                end++;
            }
            // 反转单词
            reverseString(sb, start, end - 1);
            // 更新指针到下一个单词的开始位置
            start = end + 1;
            end = start + 1;
        }
    }
}

4. 找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"

输出：0

解释："sad" 在下标 0 和 6 处匹配。

第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"

输出：-1

解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

• 1 <= haystack.length, needle.length <= 104
• haystack 和 needle 仅由小写英文字符组成

解题思路如下：力扣链接 (opens new window)

要在字符串 haystack 中找到 needle 的第一个匹配项的下标，我们可以使用暴力枚举去匹配。

1. 遍历 haystack：我们将遍历 haystack 字符串，检查每个可能的起始位置是否可以匹配 needle。
2. 匹配 needle：对于 haystack 中的每个起始位置，我们将检查接下来的字符是否与 needle 完全匹配。
3. 返回下标：一旦找到匹配，返回当前的起始下标。如果遍历结束还没有找到匹配项，则返回 -1。

• 时间复杂度：O(m*n)，n为haystack的长度，m为needle的长度。

暴力匹配代码如下

class Solution {
    public int strStr(String haystack, String needle) {
        int m = haystack.length(), n = needle.length();

        // 遍历haystack
        for (int start = 0; start < m - n + 1; start++) {
            // 找到haystack中与needle的第一个字符相同的位置
            if (haystack.charAt(start) == needle.charAt(0)) {
                // 检查从这个位置开始的子串是否与needle匹配
                if (haystack.substring(start, start + n).equals(needle)) {
                    return start; // 匹配成功，返回下标
                }
            }
        }
        return -1; // 未找到匹配
    }
}

5. 重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"

输出: true

解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"

输出: false

示例 3:

输入: s = "abcabcabcabc"

输出: true

解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

• 1 <= s.length <= 104
• s 由小写英文字母组成

解题思路如下：力扣链接 (opens new window)

这个问题可以通过暴力解法来解决。基本思路是检查字符串 s 是否可以被其子串重复若干次构成。为此，我们可以遍历所有可能的子串长度，并尝试将每个子串重复扩展，看是否能构成原字符串 s。

1. 遍历子串长度：从长度 1 开始，一直到字符串长度的一半，因为超过一半的子串无法重复两次以上。
2. 检查子串重复：对于每个可能的子串长度，检查通过重复该子串是否能得到原字符串。
3. 子串匹配判断：如果在某次迭代中，重复扩展的子串与原字符串相匹配，则返回 true。
4. 处理未找到情况：如果所有子串长度都无法满足条件，则返回 false。

• 对于每个可能的子串长度 i，算法需要比较 n / i 次子串。
• 在最坏的情况下，时间复杂度接近于 O(n^2)

暴力解法代码如下

public class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int i = 1; i <= n / 2; ++i) {
            // 只有当 s 的长度是 i 的倍数时，s 才可能由长度为 i 的子串重复构成
            if (n % i == 0) {
                boolean match = true;
                String pattern = s.substring(0, i);
                for (int j = i; j < n; j += i) {
                    // 比较每个子串是否与模式串相等
                    if (!s.substring(j, j + i).equals(pattern)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true; // 找到匹配的子串
                }
            }
        }
        return false; // 未找到匹配的子串
    }
}