Re: [閒聊] 每日leetcode

[sixB (6B)]

這題真的是

寫的非常不爽

簡單來說就是爆搜

dfs全部搜爆

或是bfs從大的開始搜

可是要記state

我選擇pruning==

太小我就不要了

class Solution {
public:
    int maxUniqueSplit(string s) {
        int len = s.length();
        //string_view sv;
        // C++20 hash:string_view

        int res = 1;
        for(int cut = (1 << (len - 1)) - 1; cut > 0; cut--){
            //cout << "cut " <<  cut << '\n';
            int head = 0;
            unordered_set<string> st;
            bool check = true;
            int cnt = 1, c = cut;
            while(c > 0){
                cnt += c&1;
                c >>= 1;
            }
            //cout << cnt << '\n';
            if (cnt <= res) continue;
            c = cut;
            for(int i = 1; i < len and check ; i++, c >>= 1){
                if(c & 1) {
                    check &= !st.count(s.substr(head, i - head));
                    //cout << head << " " << i << ", ";
                    st.insert(s.substr(head, i - head));
                    head = i;
                }
            }
            if(!check) {
                //cout << '\n';
                continue;
            }
            check &= !st.count(s.substr(head, len - head));
            //cout << head << " " << len << "; \n";
            if(check){
                res = cnt;
                //cout << "res " << res << '\n';
            }
        }

        return res;
    }

};

嗎的真的要check 2^n 次真的超躁

莫名其妙

※ 引述《JIWP (神楽めあ的錢包)》之銘言：
: 1593. Split a String Into the Max Number of Unique Substrings



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.231.184.131 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729517337.A.5BD.html
推 oin1104: 大師