LeetCode-1525-字符串的好分割数目
Miyagi Lv1
 2021-01-29 16:41:05      676 字  2 分钟  

题目地址（Leetcode-1525）

https://leetcode.com/problems/number-of-good-ways-to-split-a-string/

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
给你一个字符串s 一个分割被称为 「好分割」 当它满足：将 s 分割成 2 个字符串 p 和 q ，它们连接起来等于 s 且 p 和 q 中不同字符的数目相同。

请你返回 s 中好分割的数目

示例：
输入：s = "aacaba"
输出：2
解释：总共有 5 种分割字符串 "aacaba" 的方法，其中 2 种是好分割。
("a", "acaba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aa", "caba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aac", "aba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aaca", "ba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aacab", "a") 左边字符串和右边字符串分别包含 3 个和 1 个不同的字符。

解法

首先尝试了暴力解法，直接TLE。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int numSplits(String s) {
        int ans = 0;
        for(int i = 1;i<s.length();i++){
            if(getTypeSize(s.substring(0,i))==getTypeSize(s.substring(i,s.length()))){
                ans++;
            }
        }
        return ans;
    }
    public int getTypeSize(String s){
        Set<Character> set = new HashSet<>();
        for(char c:s.toCharArray()){
            set.add(c);
        }
        return set.size();
    }
}

改为两次遍历的方式，对比不同字母个数，代码如下：

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
class Solution {
    public int numSplits(String s) {
        int[] left = new int[256];
        int[] right = new int[256];
        int count = 0;
        // 第一次遍历，记录 字符串中每个字母出现了多少次 以及 一共出现了多少个不同的字母
        for(char c:s.toCharArray()){
            if(right[c]++==0){
                // 不同字母个数
                count++;
            }
        }
        int l = 0;
        int ans = 0;
        int r = count;
        /**
        1.第二次遍历，left数组记录当前某个字母的出现次数，l记录当前一共出现了多少个不同字母
        2.每次出现一个字母，就从right数组中减去一次该字母的出现次数，即right数组记录的是
          当前遍历位置到字符串末尾这段子字符串中某个字母的出现次数
        3.当 l==r 的时候，说明当前左边子字符串中不同字母个数等于当前右边子字符串中不同字母的个数
        */
        for(char c:s.toCharArray()){
            if(left[c]++==0){
                l++;
            }
            if(--right[c]==0){
                r--;
            }
            if(l==r){
                ans++;
            }
        }
        return ans;
    }
}

Runtime beats: 98.42%
Memory usage beats: 63.09%

 评论