LeetCode 5520 拆分字元串使唯一子字元串的數目最大 DFS

文章目錄

• • 1. 題目描述
  • • 1.1. Limit
    • 1.2. Problem Description
    • 1.3. Sample Input 1
    • 1.4. Sample Output 1
    • 1.5. Sample Input 2
    • 1.6. Sample Output 2
    • 1.7. Source
  • 2. 解讀
  • 3. 代碼

1. 題目描述

1.1. Limit

Time Limit: 2000 ms

Memory Limit: 131072 kB

1.2. Problem Description

給你一個字元串

s

，請你拆分該字元串，并傳回拆分後唯一子字元串的最大數目。

字元串

s

拆分後可以得到若幹

非空子字元串

，這些子字元串連接配接後應當能夠還原為原字元串。但是拆分出來的每個子字元串都必須是

唯一的

。

注意：

子字元串

是字元串中的一個連續字元序列。

1.3. Sample Input 1

1.4. Sample Output 1

輸出：5
解釋：一種最大拆分方法為 ['a', 'b', 'ab', 'c', 'cc'] 。像 ['a', 'b', 'a', 'b', 'c', 'cc'] 這樣拆分不滿足題目要求，因為其中的 'a' 和 'b' 都出現了不止一次。

           

1.5. Sample Input 2

1.6. Sample Output 2

輸出：2
解釋：一種最大拆分方法為 ['a', 'ba'] 。
           

1.7. Source

LeetCode 5520 拆分字元串使唯一子字元串的數目最大

2. 解讀

DFS周遊所有長度。

3. 代碼

class Solution {
public:
    unordered_set<string> st;
    int ans = 0;

    int DFS(string& str, size_t pos)
    {
        // 停止搜尋
        if (pos >= str.size()) {
            return st.size();
        }
        // 周遊所有長度
        for (size_t i = 1; i <= str.size() - pos; i++) {
            // 若未在集合中存儲
            if (st.find(str.substr(pos, i)) == st.end()) {
                // 插入集合
                st.insert(str.substr(pos, i));
                // 搜尋下一字元
                ans = max(ans, DFS(str, pos + i));
                // 将字元串從集合中删除，退回上一狀态
                st.erase(str.substr(pos, i));
            }
        }
        return ans;
    }

    int maxUniqueSplit(string s)
    {
        return DFS(s, 0);
    }
};
           

聯系郵箱：[email protected]

CSDN：https://me.csdn.net/qq_41729780

知乎：https://zhuanlan.zhihu.com/c_1225417532351741952

公衆号：複雜網絡與機器學習

歡迎關注/轉載，有問題歡迎通過郵箱交流。