字符串 | Kyle's Blog

反转字符串

来源：力扣（Leetcode）
链接：https://leetcode-cn.com/problems/reverse-string/

问题叙述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 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 码表中的可打印字符

分析

双指针，交换首尾即可

Code

class Solution {
    public void reverseString(char[] s) {
        int low = 0;
        int high = s.length - 1;
        while (low < high) {
            char tmp = s[low];
            s[low] = s[high];
            s[high] = tmp;
            low++;
            high--;
        }
    }
}

反转字符串II

来源：力扣（Leetcode）
链接：https://leetcode-cn.com/problems/reverse-string/

问题叙述

给定一个字符串 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

分析

反转部分与上题相同，我们只需要找好区间即可。
找到每个2k区间的起点start，然后反转start，start+k的区间。
但题目中说：如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
所以我们的结尾区间应该是Math.MIN(start+k,s.length-1)

Code

class Solution {
    public String reverseStr(String s, int k) {
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i += 2 * k) {
            int start = i;
            int end = Math.min(arr.length - 1, start + k - 1);
            while (start < end) {
                char tmp = arr[start];
                arr[start] = arr[end];
                arr[end] = tmp;
                start++;
                end--;
            }
        }
        return new String(arr);
    }
}

替换空格

来源：力扣（Leetcode）
链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

问题叙述

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1

输入：s = “We are happy.”
输出：“We%20are%20happy.”

限制

0 <= s 的长度 <= 10000

分析

方法一：直接用自带的replaceAll方法
方法二：创建一个StringBuilder，将原字符串中的元素挨个加入sb中，如果遇到了空格则改为添加"%20"
方法三：双指针，先遍历一遍原字符串，每遇到一个空格，便再添加两个空格的长度(将一个空格换成%20需要额外两个空间)。左指针指向原字符串末尾，右指针指向扩展至和的字符串末尾，然后依次往前遍历，只要左指针指向的字符不是空格，则将它写到右指针的位置上，遇到空格则右指针往前进行三次赋值。

Code

//方法一
class Solution {
    public String replaceSpace(String s) {
        return s.replaceAll(" ","%20");
    }
}
//方法二
class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (' ' == c) sb.append("%20");
            else sb.append(c);
        }
        return sb.toString();
    }
}
//方法三
class Solution {
    public String replaceSpace(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                str.append("  ");
            }
        }
        if (str.length() == 0) {
            return s;
        }
        int left = s.length() - 1;
        s += str.toString();
        int right = s.length() - 1;
        char[] chars = s.toCharArray();
        while (left >= 0) {
            if (chars[left] == ' ') {
                chars[right--] = '0';
                chars[right--] = '2';
                chars[right] = '%';
            } else {
                chars[right] = chars[left];
            }
            left--;
            right--;
        }
        return new String(chars);
    }
}

反转字符串里的单词

来源：力扣（Leetcode）
链接：https://leetcode-cn.com/problems/reverse-words-in-a-string/

问题叙述

给你一个字符串s，逐个翻转字符串中的所有单词。
单词是由非空格字符组成的字符串。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”
解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。

示例 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 中至少存在一个单词

进阶

请尝试使用 O(1) 额外空间复杂度的原地解法。

分析

正则表达式的使用：\s+可以匹配任何空格字符(\f换页 \n换行 \r回车 \t制表 \v垂直制表)，因为反斜杠在Java里是转义字符，所以我们这里要用"\s+"

String.join也是jdk1.8新增的一个静态方法，返回值是String类型

使用方式如下所示：
String result = String.join(“-”,“a”,“b”,“c”,“d”);
输出结果如下：a-b-c-d

也可使用如下方式：
String[] arr = {“a”,“b”,“c”,“d”};
String result = String.join(“-”,arr);
输出结果如下：a-b-c-d

参数列表：
　　1. 表示连接的符号
　　2. 表示被连接的数组（也可以是集合），或者是要连接的多个字符串

所以我们先用trim()方法清除前导空格和尾部空白，再用\s+匹配多个空格切片，将其存入list中，再用reverse()方法将list列表反转，再用空格字符连接作为返回值即可。

Code

//由于Java的String的不可变性，所以没有空间复杂度为O(1)的原地解法
class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        List<String> list = Arrays.asList(s.split("\\s+"));
        Collections.reverse(list);
        return String.join(" ", list);
    }
}

左旋转字符串

来源：力扣（Leetcode）
链接：https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/

问题叙述

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1

输入: s = “abcdefg”, k = 2
输出: “cdefgab”

示例 2

输入: s = “lrloseumgh”, k = 6
输出: “umghlrlose”

限制

1 <= k < s.length <= 10000

分析

方法一：
因为Java中String的不可变性，所以这里不能用String(效率低，占空间)，而是用StringBuilder，手动模拟即可，从n开始，将元素逐渐加入到sb中
方法二：
从n位置分为两个子串，将这两个子串换位置相加

Code

//方法一：
class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder sb=new StringBuilder();
        for (int i = n; i < n+s.length(); i++) {
            sb.append(s.charAt(i%s.length()));
        }
        return sb.toString();
    }
}
//方法二：
class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n)+s.substring(0,n);
    }
}

实现strStr(())

来源：力扣（Leetcode）
链接：https://leetcode-cn.com/problems/implement-strstr/

问题叙述

实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1

输入：haystack = “hello”, needle = “ll”
输出：2

示例 2

输入：haystack = “aaaaa”, needle = “bba”
输出：-1

示例 3

输入：haystack = “”, needle = “”
输出：0

提示

0 <= haystack.length, needle.length <= 5 * 104
haystack 和 needle 仅由小写英文字符组成

分析

大海捞针的英文版：Looking for a needle in a haystack

暴力算法：用needle串和haystack串的所有长度等于needle的子串挨个比较，为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配（可以通过设置一个flag来实现），对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。如果所有子串都匹配失败，则返回 -1。

KMP算法：难点在于k=next[k]这句，我也是查了好多资料才搞明白。
KMP

next数组也是各有不同，我这里用的是第一行这种的。
next

Code

//我是一个冷酷无情的API选手
class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}
//暴力    
class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i + m <= n; i++) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }
}

//KMP（next数组从-1开始）
class Solution {
    public void getNext(int[] next, String needle) {
        char[] ned = needle.toCharArray();
        next[0] = -1;
        int j = 0, k = -1;
        while (j < ned.length - 1) {
            if (k == -1 || ned[j] == ned[k]) {
                j++;
                k++;
                next[j] = k;
            } else k = next[k];
        }
    }

    public int strStr(String haystack, String needle) {
        if (needle.isEmpty()) return 0;
        if (haystack.isEmpty() || haystack.length() < needle.length()) return -1;
        int[] next = new int[haystack.length()];
        getNext(next, needle);
        int i = 0, j = 0;
        while (i < haystack.length() && j < needle.length()) {
            if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else j = next[j];
        }
        if (j >= needle.length()) return i - needle.length();
        else return -1;
    }
}

重复的子字符串

来源：力扣（Leetcode）
链接：https://leetcode-cn.com/problems/repeated-substring-pattern/

问题叙述

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1

输入: “abab”
输出: True
解释: 可由子字符串 “ab” 重复两次构成。

示例 2

输入: “aba”
输出: False

示例 3

输入: “abcabcabcabc”
输出: True
解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

分析

由于next数组不同，所以代码也会有些许不同。
next[len-1]=7，我们再后补一个空格，next[len]=8，此时的8就是字符串asdfasdfasdf的最长相同前后缀的长度
(len-next[len])也就是 12（字符串长度）-8（最长公共前后缀的长度）= 4 ，4刚好可以被12（字符串长度）整除，所以说明有重复字串（asdf）
说明：数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。

Code

class Solution {
   public boolean repeatedSubstringPattern(String s) {
        String str = s + s;
        return str.substring(1, str.length() - 1).contains(s);
    }
}

class Solution {
    public static void getNext(int[] next, String needle) {
        char[] ned = (needle+" ").toCharArray();
        next[0] = -1;
        int j = 0, k = -1;
        while (j < ned.length-1) {
            if (k == -1 || ned[j] == ned[k]) {
                j++;
                k++;
                next[j] = k;
            } else k = next[k];
        }
    }

    public static boolean repeatedSubstringPattern(String s) {
        int len = s.length();
        int[] next = new int[s.length()+1];
        getNext(next, s);
        if (next[len] != 0 && len % (len - (next[len])) == 0) {
            return true;
        }
        return false;
    }
}