作者sixB (6B)
看板Marginalman
標題Re: [閒聊] 每日leetcode
時間Mon Sep 23 11:22:09 2024
2707.
Extra char in a string
給一個string s , 給一個字典 dict
題幹意思要你拆s
用dp做的意思就變成
用字典的字+最少extra character拼出s
字典的字不能overlap, 可以reuse
##思路
字典建trie
s掃一遍 存下所有word的interval
sort interval
dp找min extra
// 71ms trie + dp
class trie{
public:
vector<trie*> child;
bool tail;
trie(){
child = vector<trie*>(26, nullptr);
tail = false;
}
};
class Solution {
public:
trie* root = new trie();
vector<pair<int, int>> word_idx;
vector<int> dp;
int minExtraChar(string s, vector<string>& dict) {
// put dict into trie;
build_trie(dict);
int len = s.length();
for(int i = 0; i < len; i++){
search_trie(s.substr(i), i);
}
sort(word_idx.begin(), word_idx.end());
dp = vector<int>(len, -1);
return compute_min_extra(len);
}
int compute_min_extra(int len){
int n = word_idx.size();
dp[0] = 1;
for(int i = 0, idx = 0; i < len; i++){
if(dp[i] == -1) dp[i] = dp[i-1] + 1;
else if( i > 0 ) dp[i] = min(dp[i], dp[i-1] + 1);
while(idx < n and word_idx[idx].first <= i){
//take idx
auto [head, tail] = word_idx[idx];
if(head == 0) dp[tail] = 0;
else{
if(dp[tail] == -1) dp[tail] = dp[head-1];
else dp[tail] = min(dp[tail], dp[head-1]);
}
idx++;
}
}
return dp[len-1];
}
void build_trie(vector<string>& dict){
for(string& s: dict){
trie* t = root;
for(char& c: s){
int idx = c - 'a';
if(t->child[idx] == nullptr){
t->child[idx] = new trie();
}
t = t->child[idx];
}
t->tail = true;
}
}
void search_trie(string s, int idx_l){
int len = s.length();
trie* t = root;
for(int i = 0; i < len; i++){
int idx = s[i] - 'a';
if(t->child[idx] == nullptr) break;
t = t->child[idx];
if(t->tail){
word_idx.emplace_back(idx_l, idx_l + i);
}
}
}
};
看到這種題號數字超大的都喪心病狂==
難度感覺都不能參考
昨天那題hard概念好懂 可是我想好久
今天這題寫了一個trie
搜完還要dp計才不會TLE
要多忙
從9.寫到11.= =
--
我TLE了
/*
// dfs TLE
compute_min_extra(-1, 0, 0, len); // (last_get_word_idx[i], next_start_idx, extra_cnt )
void compute_min_extra(int idx, int head, int cnt, int len){
//cout << idx << " " << head << " " << cnt << " " << len << '\n';
int n = word_idx.size();
if(head >= len) {
res = min(res, cnt);
return;
}
for(int i = idx + 1; i < n; i++){
if(word_idx[i].first < head) continue;
//take i
compute_min_extra(i, (word_idx[i].second + 1), (cnt + word_idx[i].first - head), len);
//not take
}
cnt += len - head;
res = min(res, cnt);
}
*/
-----
Sent from JPTT on my iPad
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727061733.A.227.html
推 Wardyal: 恨DP...恨.. 09/23 11:22
→ sixB: 看solution 作法好多喔 大家的思想都好豐富 09/23 11:25
→ sixB: 不開trie的dp好簡單:0 09/23 11:26
→ sixB: 我哭了 我先想到trie想到要dp 09/23 11:26
推 JIWP: 大師995 09/23 11:26
推 Chricey: UC2是啥東西?求解釋啦! 09/23 11:26 推 DJYOSHITAKA: 看來今天又g了 09/23 11:27
推 sustainer123: 最近有夠難 哭了 09/23 11:32
推 Che31128: 大師. 09/23 11:33
→ sixB: 媽啦純recursion 不開dp也會過 我吐了 09/23 11:35
推 Kroner: 求推薦UC2,樓下請提供三家 09/23 11:35 → sixB: dp n*m 而已 而且又短又好懂:( 09/23 11:41
→ sixB: 你們可以忽視我的trie了 09/23 11:41