1525字符串的好分割数目（字典计数、动态规划）

1. 问题描述&＃xff1a;

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

示例 1&＃xff1a;

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

示例 2&＃xff1a;

输入&＃xff1a;s &＃61; "abcd"
输出&＃xff1a;1
解释&＃xff1a;好分割为将字符串分割成 ("ab", "cd") 。

示例 3&＃xff1a;

输入&＃xff1a;s &＃61; "aaaaa"
输出&＃xff1a;4
解释&＃xff1a;所有分割都是好分割。

示例 4&＃xff1a;

输入&＃xff1a;s &＃61; "acbadbaada"
输出&＃xff1a;2

提示&＃xff1a;

• s 只包含小写英文字母。
• 1 <&＃61; s.length <&＃61; 10^5

2. 思路分析&＃xff1a;

① 分析题目可以知道我们需要计算[0, i]与[i &＃43;1, len(s)]的不同字符的个数&＃xff0c;所以这是一个计数问题&＃xff0c;对于计数的相关问题&＃xff0c;是可以使用哈希表记录键值对的映射关系进行计数&＃xff0c;也就是将出现相同的键进行计数&＃xff0c;java或者c&＃43;&＃43;语言可以使用map进行计数&＃xff0c;对于python语言可以使用字典dict进行计数&＃xff0c;只是计数的时候使用的数据结构是不一样的&＃xff0c;但是作用效果是一样的&＃xff0c;基于这个想法比较容易想到的是使用两个字典来记录左边与右边出现的字符的数目&＃xff0c;所以可以先预处理一下这两个字典dic1与dic2&＃xff0c;dic1记录字符串的第一个字符出现的次数&＃xff0c;dic2记录字符串中第二个字符到len(s)位置字符的出现的次数&＃xff0c;然后从字符串s的第二个位置开始模拟字符串的好分割过程&＃xff0c;对于当前的字符c&＃xff0c;dic1[c] &＃43;&＃61; 1&＃xff0c; dic2[c] -&＃61; 1&＃xff0c;并且需要注意的是当前字符c在字典dic2出现的次数为1的时候那么就需要删除掉dic2中的这个键&＃xff0c;这样我们才可以根据两个字典的长度判断出不同字符的数目&＃xff0c;我们在判断出满足两个字典长度相同的时候对结果进行加1即可

② 所以我们两遍遍历字符串 &＃43; 两个字典来长度检查不同字符的数目

③ 除了上面的这个解法之外&＃xff0c;力扣官方提供了一个动态规划的解法&＃xff0c;我感觉这个思路也是蛮好的&＃xff0c;容易理解&＃xff0c;可以学习学习&＃xff0c;我的理解如下&＃xff1a;它是有一种递推的思想在里面&＃xff0c;这个其实也是动态规划能够解决的问题的一个特点&＃xff0c;首先声明两个长度为26的列表&＃xff08;相当于是字典&＃xff09;对出现过的字母进行标记&＃xff08;这样也是为了后面的的计数方便&＃xff09;&＃xff0c;我们在遍历字符串的过程中由前一个位置不同字符出现的次数推出当前这个位置不同字符出现的次数&＃xff0c;可以先判断当前字符在字母表中对应的位置是否出现过&＃xff0c;如果未出现过那么在上一个位置的不同字符出现的次数进行加1即可&＃xff0c;假如出现过那么维持上一个的不同字符出现的次数&＃xff0c;这样一遍遍历字符串s就可以知道从0到字符串末尾的位置上不同字符出现的次数&＃xff0c;因为是比较左右两边的情况&＃xff0c;所以自然想到从末尾的位置开始以同样的方法记录不同字符出现的次数&＃xff0c;这样两次遍历之后才可以比较左右两边的不同字符串的次数

3. 代码如下&＃xff1a;

import collectionsclass Solution:def numSplits(self, s: str) -> int:if not s: return 0dic1, dic2 &＃61; collections.defaultdict(int), collections.defaultdict(int)dic1[s[0]] &＃43;&＃61; 1for i in range(1, len(s)):dic2[s[i]] &＃43;&＃61; 1res &＃61; 0if len(dic1) &＃61;&＃61; len(dic2): res &＃43;&＃61; 1for i in range(1, len(s) - 1):dic1[s[i]] &＃43;&＃61; 1# 当检查当前待删除的字符在dic2中的次数为1的时候应该将dic2中对应的键删除掉这样在统计长度的时候才不会统计进来if dic2[s[i]] &＃61;&＃61; 1: del dic2[s[i]]if len(dic1) &＃61;&＃61; len(dic2): res &＃43;&＃61; 1return res

官方动态规划代码&＃xff1a;

class Solution:def numSplits(self, s: str) -> int:n &＃61; len(s)left, right &＃61; [0] * (n &＃43; 2), [0] * (n &＃43; 2)rec_left &＃61; [False] * 26rec_right &＃61; [False] * 26for i in range(1, n &＃43; 1):c &＃61; ord(s[i - 1]) - ord("a")if rec_left[c]:left[i] &＃61; left[i - 1]else:rec_left[c] &＃61; Trueleft[i] &＃61; left[i - 1] &＃43; 1for i in range(n, 0, -1):c &＃61; ord(s[i - 1]) - ord("a")if (rec_right[c]):right[i] &＃61; right[i &＃43; 1]else:rec_right[c] &＃61; Trueright[i] &＃61; right[i &＃43; 1] &＃43; 1ret &＃61; sum(1 for i in range(1, n) if left[i] &＃61;&＃61; right[i &＃43; 1])return ret