X

LEETCODE 1525. Number of Good Ways to Split a String 解题思路分析

题目大意:

字符串的好分割数目

给你一个字符串 s ,一个分割被称为 「好分割」 当它满足:将 s 分割成 2 个字符串 p 和 q ,它们连接起来等于 s 且 p 和 q 中不同字符的数目相同。

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

示例 1:

输入: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 个不同的字符。

示例 2:

输入:s = "abcd"
输出:1
解释:好分割为将字符串分割成 ("ab", "cd") 。

示例 3:

输入:s = "aaaaa"
输出:4
解释:所有分割都是好分割。

示例 4:

输入:s = "acbadbaada"
输出:2

提示:

  • s 只包含小写英文字母。
  • 1 <= s.length <= 10^5

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1525

解题思路分析:

将字符串分割成2个非空子串的方式无非只存在(length-1)种,即从第一个元素后切一刀,第二个元素后切一刀…倒数第二个元素后切一刀。我们使用2个数组分别统计两个子串中每种字符的个数,初始时,我们默认左子串长度为0,右子串为整个字符串,首先统计出右子串中所有字符的个数。接下来开始从首元素向后循环分割位置,指针每向后移动一位,代表当前字符会从右子串移动至左子串,因此,该字符在右侧中的个数减一,同时在左侧中的个数加一。个数更新后,查看两个部分的字符种类数是否相同,如果相同,返回结果加一即可。

实现代码:

public int numSplits(String s) {
    int[] countLeft=new int[26];  // 统计左半部分子串中每种字符的个数
    int[] countRight=new int[26];  // 统计右半部分子串中每种字符的个数
    char[] arr=s.toCharArray(); // 为了方便,将字符串转为字符数组
    // 初始时默认左子串为空,右子串为整个字符串
    // 因此统计整个字符串中每种字符的个数,并存入countRight
    for(int i=0;i<arr.length;i++){
        countRight[arr[i]-'a']++; // 当前字符个数加一
    }
    int res=0; // 返回结果
    for(int i=0;i<arr.length;i++){ // 循环每一种分割方式
        // 当前字符(从右子串移动到左子串)
        int c=arr[i]-'a';
        countLeft[c]++; // 左子串中该字符个数加一
        countRight[c]--; // 右子串中该字符个数加一
        // 如果当前是好的分割,返回结果加一
        if(isGood(countLeft,countRight)) res++;
    }
    return res;
}
// 查看当前分割是否为好分割
boolean isGood(int[] countLeft, int[] countRight){
    int count1=0;
    for(int c : countLeft){
        if(c>0) count1++;
    }
    int count2=0;
    for(int c : countRight){
        if(c>0) count2++;
    }
    return count1==count2;
}

本题解法执行时间为17ms。

Runtime: 17 ms, faster than 59.59% of Java online submissions for Number of Good Ways to Split a String.

Memory Usage: 39.4 MB, less than 94.20% of Java online submissions for Number of Good Ways to Split a String.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1525-number-of-good-ways-to-split-a-string-解题思路分析/
Categories: leetcode
kwantong: