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.= =