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