leetcode1525. 字符串的好分割數目

給你一個字符串 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

---

方法：哈希集合

思路：

本題可以直接使用模擬來解決。

我們可以知道，長度為n的字符串，可以有n-1種分割方式。

我們從頭開始遍歷，使用一個集合（哈希表）word來保存目前遍歷到的字符串中存在的字符（集合會將重復的字符過濾）。

使用一個長度為n的數組begin，begin[i]表示s[:i+1]子串中存在的不同字符數（即集合word此時的長度）。

然后我們將word集合清空，從s的最后往前遍歷，直到s[1]（因為遍歷到s[0]的話，右側字符串為s，左側字符串不存在，不符合題意），加入遍歷到字符s[i]，那么此時word的長度即為s[i:]子串中的不同字符數。此時如果len(word) = begin[i-1]，那么即是一種好分割。

統計所有的好分割數，返回即可。

• 遍歷了兩次，而對集合求長度的時間復雜度為O(1)，所以總的時間復雜度為O(2n)，漸進時間復雜度為O(n)。
• 使用了一個集合和數組，空間復雜度為O(n)。

代碼：

Python3：

class Solution:def numSplits(self, s: str) -> int:res = 0n = len(s)# begin[i]存放s[:i+1]中不同字符的數量begin = [0 for _ in range(n)]word = set()for i in range(n):word.add(s[i])begin[i] = len(word)word.clear()# 下面開始從后往前遍歷，統計右半部分的情況，i的時候，len(word)即s[i:]的不同字符數# 與之相匹配的即為begin[i-1]，如果兩者相等，則為好分割。for i in range(n-1,0,-1):word.add(s[i])if begin[i-1] == len(word):res += 1return res

cpp：

class Solution { public:int numSplits(string s) {int res = 0;int n = s.size();// begin[i]存放s[:i+1]中不同字符的數量auto begin = vector<int>(n,0);unordered_set<char> word;for (int i = 0; i < n-1; ++i){word.insert(s[i]);begin[i] = word.size();}word.clear();// 下面開始從后往前遍歷，統計右半部分的情況，i的時候，len(word)即s[i:]的不同字符數// 與之相匹配的即為begin[i-1]，如果兩者相等，則為好分割。for (int i=n-1 ; i > 0; --i){word.insert(s[i]);if (begin[i-1] == word.size()) res += 1;}return res;} };

結果：

總結

以上是生活随笔為你收集整理的c字符串分割成数组_leetcode第31双周赛第三题leetcode1525. 字符串的好分割数目的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。