Re: [闲聊] 每日leetcode

楼主: sixB (6B)   2024-09-23 11:22:09
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.= =
作者: Wardyal (Wardyal)   2023-09-23 11:22:00
恨DP...恨..
楼主: sixB (6B)   2024-09-23 11:25:00
看solution 作法好多喔 大家的思想都好丰富不开trie的dp好简单:0我哭了 我先想到trie想到要dp
作者: JIWP (JIWP)   2024-09-23 11:26:00
大师995
作者: DJYOSHITAKA (Evans)   2024-09-23 11:27:00
看来今天又g了
作者: sustainer123 (caster)   2024-09-23 11:32:00
最近有够难 哭了
作者: Che31128 (justjoke)   2024-09-23 11:33:00
大师.
楼主: sixB (6B)   2024-09-23 11:35:00
妈啦纯recursion 不开dp也会过 我吐了dp n*m 而已 而且又短又好懂:(你们可以忽视我的trie了

Links booklink

Contact Us: admin [ a t ] ucptt.com