leetcode——字符串

Posted on Edited on In Word count in article: 10k Reading time ≈ 9 mins.

前言

记录一下leetcode字符串部分题目的刷题笔记，顺序参考代码随想录中，但不仅限于这些，可以扩展记录。

344. 反转字符串

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

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

示例 1：

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

思路：双指针

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public void reverseString(char[] s) {
        int left = 0  ,len = s.length;
        int right = len - left - 1;
        while(left <= right){
            char temp = s[left];
            s[left++] = s[right];
            s[right--] = temp;
        }
    }
}
  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗：48.2 MB, 在所有 Java 提交中击败了35.53%的用户
  • 通过测试用例：477 / 477

541. 反转字符串 II

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

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

示例 1：

1
2
输入：s = "abcdefg", k = 2
输出："bacdfeg"

思路：双指针+模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public String reverseStr(String s, int k) {
        int len = s.length();
        char[] arr = s.toCharArray();
        for(int i = 0;i < len; i += 2*k){
            reverse(arr, i , Math.min(i+k,len)-1);
        }
        return new String(arr);
    }

    public void reverse(char[] arr,int left, int right){
        while(left < right){
            char temp = arr[left];
            arr[left++] = arr[right];
            arr[right--] = temp;
        }
    }
}
  • 执行用时：1 ms, 在所有 Java 提交中击败了63.60%的用户,O(N)
  • 内存消耗：41.4 MB, 在所有 Java 提交中击败了27.37%的用户，O（1）
  • 通过测试用例：60 / 60

剑指 Offer 05. 替换空格

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

1
2
输入：s = "We are happy."
输出："We%20are%20happy."

思路：直接模拟

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
class Solution {
    public String replaceSpace(String s) {
        int len = s.length();
        char[] arr = new char[len*3];
        int size = 0;
        for(int i = 0 ; i<len ; i++){
            char c = s.charAt(i);
            if (c == ' '){
                arr[size++] = '%';
                arr[size++] = '2';
                arr[size++] = '0';
            }else{
                arr[size++] = c;
            }
        }
        String newStr = new String(arr,0,size);
        return newStr;
    }
}
//方法2
class Solution {
    public String replaceSpace(String s) {
        if (s == null) {
            return null;
        }
		//选用 StringBuilder 单线程使用，比较快，选不选都行
        StringBuilder sb = new StringBuilder();
		//使用 sb 逐个复制 str ，碰到空格则替换，否则直接复制
        for (int i = 0; i < s.length(); i++) {
		//str.charAt(i) 为 char 类型，为了比较需要将其转为和 " " 相同的字符串类型
        //if (" ".equals(String.valueOf(str.charAt(i)))){
            if (s.charAt(i) == ' ') {
                sb.append("%20");
            } else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

  • 内存消耗：39.4 MB, 在所有 Java 提交中击败了39.91%的用户

  • 通过测试用例：27 / 27

151. 颠倒字符串中的单词

给你一个字符串 s ，颠倒字符串中 单词 的顺序。

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

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

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

示例 1：

输入：s = “the sky is blue”
输出：”blue is sky the”

思路1：直接使用相关方法模拟

利用Java语言中已经写好的一些方法来解决

1
2
3
4
5
6
7
8
9
10
class Solution {
    public String reverseWords(String s) {
        //trim方法用于移除字符串两端多余的空格
        s = s.trim();
        //split方法中分割一个或多个空格用"\\s+"
        List<String> ans = Arrays.asList(s.split("\\s+"));
        Collections.reverse(ans);
        return String.join(" ",ans);
    }
}
  • 时间复杂度：O(n)O(n)，其中 nn 为输入字符串的长度。
  • 空间复杂度：O(n)O(n)，用来存储字符串分割之后的结果。

思路2：自写对应方法

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
class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = trimSpaces(s);

        // 翻转字符串
        reverse(sb, 0, sb.length() - 1);

        // 翻转每个单词
        reverseEachWord(sb);

        return sb.toString();
    }

    public StringBuilder trimSpaces(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 tmp = sb.charAt(left);
            sb.setCharAt(left++, sb.charAt(right));
            sb.setCharAt(right--, tmp);
        }
    }

    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，去找下一个单词
            start = end + 1;
            ++end;
        }
    }
}

  • 时间复杂度：O(n)，其中 n 为输入字符串的长度。

  • 空间复杂度：Java 和 Python 的方法需要 O(n) 的空间来存储字符串，而 C++ 方法只需要 O(1) 的额外空间来存放若干变量。

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

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

示例 1：

1
2
输入: s = "abcdefg", k = 2
输出: "cdefgab"

思路1：字符串切片函数

1
2
3
4
5
class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n,s.length()) + s.substring(0,n);
    }
}

思路2：列表遍历拼接

若面试规定不允许使用 切片函数 ，则使用此方法

1
2
3
4
5
6
7
8
9
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();
    }
}

思路3：字符串遍历拼接

若规定 Java 只能用 String ，则使用此方法。

1
2
3
4
5
6
7
8
9
class Solution {
    public String reverseLeftWords(String s, int n) {
        String ans = "";
        for(int i = n ; i < n + s.length();i++){
            ans += s.charAt(i % s.length());
        }
        return ans;
    }
}

三种方法的时间效率：1>2>3

通过 54 ms 42.2 MB Java 2022/05/09 11:18 添加备注
通过 6 ms 41.4 MB Java 2022/05/09 11:15 添加备注
通过 0 ms 41.4 MB Java 2022/05/09 11:11 添加备注

28. 实现 strStr()

实现 strStr() 函数。

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

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1：

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

思路1：直接暴力匹配

使用一个长为needle.length()的窗口来对haystack进行对比匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int strStr(String haystack, String needle) {
        if(haystack == "" || needle == ""){
            return 0;
        }
        if(haystack.length() < needle.length()) return -1;
        int len = needle.length();
        int left = 0 , right = len;
        while(left < haystack.length()-len+1){
            if(haystack.substring(left,right).equals(needle)){
                return left;
            }else{
                left++;
                right++;
            }
        }
        return -1;
    }
}

思路2：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
class Solution {
    //前缀表（不减一）Java实现
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        int[] next = new int[needle.length()];
        getNext(next, needle);

        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && needle.charAt(j) != haystack.charAt(i)) 
                j = next[j - 1];
            if (needle.charAt(j) == haystack.charAt(i)) 
                j++;
            if (j == needle.length()) 
                return i - needle.length() + 1;
        }
        return -1;

    }
    
    private void getNext(int[] next, String s) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i)) 
                j = next[j - 1];
            if (s.charAt(j) == s.charAt(i)) 
                j++;
            next[i] = j; 
        }
    }
}

459. 重复的子字符串

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

示例 1:

输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。

思路1：字符串匹配

小技巧：

1
2
3
4
5
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        return (s+s).indexOf(s,1) != s.length();
    }
}

思路2：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
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        if (s.equals("")) return false;

        int len = s.length();
        // 原串加个空格(哨兵)，使下标从1开始，这样j从0开始，也不用初始化了
        s = " " + s;
        char[] chars = s.toCharArray();
        int[] next = new int[len + 1];

        // 构造 next 数组过程，j从0开始(空格)，i从2开始
        for (int i = 2, j = 0; i <= len; i++) {
            // 匹配不成功，j回到前一位置 next 数组所对应的值
            while (j > 0 && chars[i] != chars[j + 1]) j = next[j];
            // 匹配成功，j往后移
            if (chars[i] == chars[j + 1]) j++;
            // 更新 next 数组的值
            next[i] = j;
        }

        // 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值
        if (next[len] > 0 && len % (len - next[len]) == 0) {
            return true;
        }
        return false;
    }
}

详解见：代码随想录——重复的子字符串