LeetCode：字符串篇

总结

• 反转、替换空格
  • 双指针法
• 翻转单词顺序、左旋转字符串
  • 反转字符串+反转单词
• 第一个子字符串匹配项、重复子字符串
  • KMP算法

344 (简单)反转字符串

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

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

/**
 * 双指针法：头尾交换
 */
class Solution {
    public void reverseString(char[] s) {
        //方式一：头尾交换，异或预算
        int i=0,j=s.length-1;
        while(i<j){
            s[i]^=s[j];
            s[j]^=s[i];
            s[i]^=s[j];
            i++;
            j--;
        }
        //方式二：头尾交换，使用缓冲字符
        // for(int i=0;i
        //     int j=s.length-1-i;
        //     char buf=s[i];
        //     s[i]=s[j];
        //     s[j]=buf;
        // }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

541 (简单)反转字符串 II

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

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

class Solution {
    /**
 	 *	方式一：直接在字符数组上使用异或进行反转
 	 *		1.转换为字符数组
 	 *		2.每次遍历2*k个元素的区间，直接将前k个元素进行反转
 	 *		注意最后一个区间的处理
 	 */
    public String reverseStr(String s, int k) {
        char[] arr=s.toCharArray();
        //每次遍历2*k个元素的区间，将该区间前k个元素进行反转
        for(int i=0;i<=arr.length-1;i+=2*k){
            //前k个元素的头索引
            int head=i;
            //前k个元素的尾索引：不足k个元素，取数组尾索引
            int tail=arr.length-1<i+k-1?arr.length-1:i+k-1;
            //开始反转
            while(head<tail){
                arr[head]^=arr[tail];
                arr[tail]^=arr[head];
                arr[head]^=arr[tail];
                head++;
                tail--;
            }
        }
        String result=new String(arr);
        return result;
    }
    //方式二：循环每2*k的区间，截取转换为StringBuilder反转并拼接
    public String reverseStr2(String s, int k) {
        StringBuilder result=new StringBuilder();
        //开始位置
        int start=0;
        int length=s.length();
        while(start<length){
            //位置k
            int mid=start+k-1>length-1?length-1:start+k-1;
            //位置2k
            int end=start+2*k-1>length-1?length-1:start+2*k-1;
            //截取前k个
            StringBuilder buf=new StringBuilder(s.substring(start,mid+1));
            //反转并拼接前k个
            result.append(buf.reverse());
            //拼接后k个
            result.append(s.substring(mid+1,end+1));
            //循环下一个2*k的区间
            start+=2*k;
        }
        return result.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

剑指 Offer 05 (简单)替换空格

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

/**
 * 推荐第一种方式：空间复杂度O(n)
 */
class Solution {
    //方式一：转换为字符数组，扩容数组并在数组上进行替换
    public String replaceSpace(String s) {
        //1.扩容：找到s串的空格，每个空格增加两个空格
        StringBuilder buf=new StringBuilder();
        for(int i=0;i<s.length();i++){
            if(' '==s.charAt(i)) buf.append("  ");
        }
        //2.判断：没有空格直接返回
        if(buf.length()==0) return s;
        //3.将扩容的空格添加到s串尾部
        s+=buf.toString();
        //4.双指针替换
        char[] result=s.toCharArray();
        int head=result.length-buf.length()-1;
        int tail=result.length-1;
        while(head!=tail){
            if(result[head]==' '){
                head--;
                result[tail--]='0';
                result[tail--]='2';
                result[tail--]='%';
            }else{
                result[tail]=result[head];
                head--;
                tail--;
            }
        }
        return new String(result);

    }
    //方式二：遍历寻找+拼接
    //直接遍历拼接：最简单
    public String replaceSpace2(String s) {
        StringBuilder result=new StringBuilder();
        for(int i=0;i<s.length();i++){
            if(' '==s.charAt(i)){
                result.append("%20");
            }else{
                result.append(s.charAt(i));
            }
        }
        return result.toString();
    }
    //自己写的：使用string类的方法，给复杂化了
    //使用indexOf(String,int)
    public String replaceSpace3(String s) {
        StringBuilder result=new StringBuilder();
        int start=0;
        int local=0;
        while((local=s.indexOf(" ",start))!=-1 && start<s.length()){
            result.append(s.substring(start,local));
            result.append("%20");
            start=local+1;
        }
        //start-s.length() 找不到空格的情况
        result.append(s.substring(start,s.length()));
        return result.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

151 (中等)翻转字符串里的单词

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

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

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

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

/**
 *	方法一：1.去除首尾空字符及中间多余空格 2.反转字符串 3.反转单词
 *	方法二：使用substring，空间复杂度O(n),不建议
 */

//方法一：1.去除首尾及多余空格 2.反转字符串 3.反转单词
class Solution {
    public String reverseWords2(String s) {
        //1.去除首尾及多余空格
        StringBuilder sb=trimStrengthen(s);
        //2.反转字符串
        reverseStr(sb,0,sb.length()-1);
        //3.反转单词
        reverseWord(sb);
        return sb.toString();
    }
    //1.去除首尾及多余空格
    private StringBuilder trimStrengthen(String s){
        StringBuilder sb=new StringBuilder();
        int len=s.length();
        int start =0;
        int end=len-1;
        //定位s串第一个非空索引：出除头部空格
        while(s.charAt(start)==' ') start++;
        //定位s串最后一个非空字符索引：去除尾部空格
        while(s.charAt(end)==' ') end--;
        //将start-end中的字符进行添加：去除中间多余空格
        while(start<=end){
            char c=s.charAt(start);
            if(c!=' ' || sb.charAt(sb.length()-1)!=' ') sb.append(c);
            start++;
        }
        return sb;
    }
    //2.反转字符串 
    private void reverseStr(StringBuilder sb,int startIndex,int endIndex){
        while(startIndex<endIndex){
            char c=sb.charAt(startIndex);
            sb.setCharAt(startIndex,sb.charAt(endIndex));
            sb.setCharAt(endIndex,c);
            startIndex++;
            endIndex--;
        }
    }
    //3.反转单词
    private void reverseWord(StringBuilder sb){
        int start=0;
        int end=start+1;
        while(end<sb.length()){
            //遇到空格，反转前面的单词
            if(sb.charAt(end)==' '){
                reverseStr(sb,start,end-1);
                start=end+1;
                end=start+1;
                continue;
            }
            //是最后一个单词找不到空格了，反转最后一个单词
            if(end==sb.length()-1){
                reverseStr(sb,start,end);
                return;
            }
            end++;
        }
    }
}
//方法二：逻辑比较复杂
//substring 申请了额外空间O(n),不建议使用
class Solution {
    public String reverseWords(String s) {
        char[] arr=s.toCharArray();
        int len=s.length();

        StringBuilder sb=new StringBuilder();
        //定位单词的尾索引
        int tail=-1;
        //是否是第一个单词
        boolean isFirst=true;
        //1.从尾部开始遍历字符
        for(int i=len-1;i>=0;i--){
            //2.是非空字符，且是单词尾字符
            if(' '!=s.charAt(i) && tail==-1){
                //2.1 不是第一个单词，添加空字符
                if(!isFirst){
                    sb.append(" ");
                }
                //2.2 是第一个单词，改变变量值
                else{
                    isFirst=false;
                }
                //2.3 保存尾字符索引
                tail=i;
            }
            //3.是空字符，且存在单词尾索引
            if(' '==s.charAt(i) && tail!=-1){
                //3.1 截取单词并添加
                sb.append(s.substring(i+1,tail+1));
                //3.2 重置单词尾索引
                tail=-1;
            }
            //4.是最后一个字符，且存在单词尾索引
            if(i==0 && tail!=-1){
                //4.1 截取最后一个单词
                sb.append(s.substring(0,tail+1));
            }
        }
        return sb.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

剑指 Offer 58 - II (简单)左旋转字符串

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

class Solution {
    //方式一：整体反转+局部反转
    public String reverseLeftWords(String s, int n) {
        char[] arr=s.toCharArray();
        //1.整体反转
        int start=0;
        int end=s.length()-1;
        while(start<end){
            arr[start]^=arr[end];
            arr[end]^=arr[start];
            arr[start]^=arr[end];
            start++;
            end--;
        }
        //2.局部反转
        start=0;
        end=arr.length-n-1;
        while(start<end){
            arr[start]^=arr[end];
            arr[end]^=arr[start];
            arr[start]^=arr[end];
            start++;
            end--;
        }
        start=arr.length-n;
        end=arr.length-1;
        while(start<end){
            arr[start]^=arr[end];
            arr[end]^=arr[start];
            arr[start]^=arr[end];
            start++;
            end--;
        }
        return new String(arr);
    }
    //方式二：保存前n个字符+后面字符前移+n个字符添加到末尾
    //使用substring，空间复杂度O(n)，不建议
    public String reverseLeftWords1(String s, int n) {
        char[] arr=s.toCharArray();
        //1.保存前n个字符
        String buf=s.substring(0,n);
        //2.将后部分字符串前移
        int before=0;
        int after=n;
        while(after<arr.length){
            arr[before]^=arr[after];
            arr[after]^=arr[before];
            arr[before]^=arr[after];
            before++;
            after++;
        }
        //3.将前n个字符添加到末尾
        for(int i=0;i<buf.length();i++){
            arr[before]=buf.charAt(i);
            before++;
        }
        return new String(arr);
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

28 (中等)实现 strStr()

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

/**
 * 面试题：当 needle 为null时，应该返回什么？0
 */
class Solution {
    //方法一：KMP
    public int strStr(String haystack, String needle) {
        //1.获取next数组
        int[] next=new int[needle.length()];
        getNext(next,needle);
        int j=0;
        for(int i=0;i<haystack.length();i++){
            while(j>0 && haystack.charAt(i)!=needle.charAt(j)){
                j=next[j-1];
            }
            if(haystack.charAt(i)==needle.charAt(j)){
                j++;
            }
            if(j==needle.length()) return i+1-needle.length();
        }
        return -1;
    }
    private void getNext(int next[],String str){
        int j=0;
        next[0]=0;
        for(int i=1;i<str.length();i++){
            //如果前缀与后缀匹配不成功：则前缀往前遍历，通过next数组查找可能与后缀相同的元素
            while(j>0 && str.charAt(i)!=str.charAt(j)){
                j=next[j-1];
            }
            //如果前缀与后缀匹配成功：则前缀与后缀都后移，继续匹配并叠加公共子串的长度
            if(str.charAt(i)==str.charAt(j)){
                j++;
            }
            next[i]=j;
        }
    }
    //方法二：蛮力法
    public int strStr2(String haystack, String needle) {
        int hlen=haystack.length();
        int nlen=needle.length();
        for(int i=0;i<hlen-nlen+1;i++){
            int j=0;
            while(j<nlen){
                if(haystack.charAt(i+j)!=needle.charAt(j)) break;
                if(j==nlen-1) return i;
                j++;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

459 (简单)重复的子字符串

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

//方法一：KMP
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int len=s.length();
        int[] next=new int[len];
        int j=0;
        for(int i=1;i<len;i++){
            while(j>0 && s.charAt(i)!=s.charAt(j)) j=next[j-1];
            if(s.charAt(i)==s.charAt(j)) j++;
            next[i]=j;
        }
        int l=len-next[len-1];
        //注意排除无公共子串的情况
        if(len%l==0 && l!=len) return true;
        else return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17