字符串系列第一弹

一、Java 字符串介绍

String、StringBuilder、StringBuffer 要用熟练，这里再总结一下。

字符串处理有很多的库函数，要掌握这些函数的底层实现大致过程。

StringBuffer 和 StringBuilder

相同点：两个类的方法是一致的；都是存储字元的容器。在使用上几乎一样。

不同点：

StringBuffer 是线程安全的，效率低；Stringbuilder是线程不安全的，效率高。在单线程程序里推荐使用，比如leetcode 做题时。
StringBuffer 是jdk1.0出现的，StringBuilder 是jdk1.5 出现的。

1.1 String 常用方法

这里总结很全面

字符与字符串

1
2
3
4
5

public String (char[] value)

public char charAt(int index)

public char[] toCharArray()
Copy

字节与字符串

字符串比较

1
2
3

public boolean equals (Object anObject)

public int compareTo(String anotherString)
Copy

字符串查找

1
2
3
4

public int indexOf(String str)

public int lastIndexOf(String str)
....
Copy

字符串截取
字符串替换
字符串拆分
其他操作方法

1.2 StringBuilder 常用方法

构造方法

1
2
3

StringBuilder sb = new StringBuilder();
StringBuilder sb2 = new StringBuilder("sb2:fsd");
StringBuilder sb3 = new StringBuilder(10);
Copy

增加

1
2
3

append(boolean b) 将 boolean参数的字符串表示形式追加到序列中,可以是任意类型String、char、int

insert​(int offset, char c) 指定插入的索引值，插入对应的内容，可以是任意类型 String、char、int
Copy

删除

1
2
3

delete (int start, int end) 根据指定的开始索引和结束索引删除对应的内容

deleteCharAt(int index) 根据指定的索引值删除一个字元
Copy

修改

1
2
3
4
5
6
7

replace (int start, int end, String str) 使用指定的String 的字符替换子字符串的字符

reverse() 翻转

setCharAt(int index, char ch) 把指定索引值的字符替换成指定的字符

substring(int start, int end) 根据索引提取子串
Copy

检查

1
2
3
4
5
6
7

 int indexOf(String str) 返回指定字符串str 第一次出现的索引
 int indexOf(String str, int fromIndex)  查詢指定字串第一次出現的索引值，並且指定查詢開始的索引位置
 int capacity()  返回容量大小
 char charAt(int index) 返回指定索引处的字符
 int lastIndexOf(String str) 返回指定字符串str 最后一次出现的索引
 int length()
 String toString()  把字串類的內容轉換成字串返回
Copy

二、反转字符串

这个题目就是双指针的用法，注意交换数字的技巧。

344. 反转字符串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while (l < r) {
            s[l] ^= s[r];  //构造 a ^ b 的结果，并放在 a 中
            s[r] ^= s[l];  //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
            s[l] ^= s[r];  //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换
            l++;
            r--;
        }
    }
}
Copy

541. 反转字符串 II

利用 StringBuilder

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public String reverseStr(String s, int k) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i += 2*k) {
            StringBuilder temp = new StringBuilder();
            int firstK = Math.min(i+k, s.length());
            int secondK = Math.min(i+2*k, s.length());
            temp.append(s.substring(i, firstK));
            temp.reverse();
            sb.append(temp);
            if (firstK < secondK) {
                sb.append(s.substring(firstK, secondK));
            }
        }
        return sb.toString();
    }
}
Copy

利用 char[]

更容易理解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        for(int i = 0; i < ch.length; i += 2 * k){
            int start = i;
            //这里是判断尾数够不够k个来取决end指针的位置
            int end = Math.min(ch.length - 1, start + k - 1);
            //用异或运算反转 
            while(start < end){
                ch[start] ^= ch[end];
                ch[end] ^= ch[start];
                ch[start] ^= ch[end];
                start++;
                end--;
            }
        }
        return new String(ch);
    }
}
Copy

151. 翻转字符串里的单词

自己遍历，不利用split

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        int left = s.length() -  1, right = s.length() - 1;
        while (right >= 0) {
            if (left == right && s.charAt(left) == ' ') {
                left--;
                right--;
                continue;
            }
            if (left >= 0 && s.charAt(left) != ' ') {
                left--;
            } else {
                sb.append(s.substring(left+1, right+1) + " ");
                right = left;
            }
        }
        return sb.toString().trim();
    }
}
Copy

还有的常规做法就是

去除首尾以及中间多余空格
反转整个字符串
反转单个单词

剑指 Offer 58 - II. 左旋转字符串

三次reverse就可以。

三、替换空格

剑指 Offer 05. 替换空格

利用原地的那种来实现，双指针。还可以用库函数。

四、字符串匹配

28. 实现 strStr()

KMP 解法

见KMP 算法理解，贴一下代码。

 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

class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null || haystack.length() < needle.length())
            return -1;
        if (needle.length() == 0) {
            return 0;
        }
        char[] str1 = haystack.toCharArray();
        char[] str2 = needle.toCharArray();
        int i1 = 0;
        int i2 = 0;
        int[] next = getNextArray(str2);
        while (i1 < str1.length && i2 < str2.length) {
            if (str1[i1] == str2[i2]) {
                i1++;
                i2++;
            } else if (next[i2] == -1) { // i2 == 0
                i1++;
            } else {
                i2 = next[i2];
            }
        }
        return i2 == str2.length ? i1 - i2 : -1;
    }

    public static int[] getNextArray(char[] ms) {
        if (ms.length == 1) {
            return new int[] {-1};
        }
        int[] next = new int[ms.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;		//  ms的第cn个字符
        while (i < next.length) {
            if (ms[i-1] == ms[cn]) {
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }
}
Copy

459. 重复的子字符串

 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

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        if (s == null || s.length() == 0)
            return false;
        int len = s.length();
        s = s + " ";
        int[] next = getNextArray(s.toCharArray());
        if (next[len] > 0 && len % (len - next[len]) == 0) {
            return true;
        }
        return false;
    }

    public int[] getNextArray(char[] ms) {
        if (ms.length == 1) {
            return new int[] {-1};
        }
        int[] next = new int[ms.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;		//  ms的第cn个字符
        while (i < next.length) {
            if (ms[i-1] == ms[cn]) {
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }
}
Copy

10. 正则表达式匹配

递归版本

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public boolean isMatch(String s, String p) {
        char[] str1 = s.toCharArray();
        char[] str2 = p.toCharArray();
        return helper(str1, str2, 0, 0);
    }

    public boolean helper(char[] str1, char[] str2, int i, int j) {
        if (j == str2.length) return i == str1.length;

        if (j + 1 < str2.length && str2[j+1] == '*') {
            if (i < str1.length && (str2[j] == '.' || str2[j] == str1[i]))
                return helper(str1, str2, i, j+2) || helper(str1, str2, i+1, j);
            else 
                return helper(str1, str2, i, j+2);
        }
        if (i < str1.length && (str2[j] == '.' || str1[i] == str2[j]))
            return helper(str1, str2, i+1, j+1);
        return false;
    }
}
Copy

迭代版本
Copy
动态规划