推 DJYOSHITAKA: 你是大濕... 05/24 16:56
推 SecondRun: 大師 05/24 16:56
推 digua: 大師 05/24 17:06
※ 引述《ray90514 ()》之銘言：
: 1255. Maximum Score Words Formed by Letters
: 今天是hard
: 紀錄所有可能的組合算一個最大值 重複的跳過
: 不過一開始寫成flag = 害我卡住不知道哪裡錯==
: class Solution {
: public:
: int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>&
: score) {
: unordered_set<string> st;
: vector<pair<string, int>> dp;
: string abc(26, 0);
: for(char c : letters){
: abc[c - 'a']++;
: }
: dp.push_back({string(26, 0), 0});
: int ans = 0;
: string s(26, 0);
: for(int i = 0; i < words.size(); i++){
: for(int j = dp.size() - 1; j >= 0; j--){
: bool flag = false;
: pair<string, int> p = dp[j];
: for(char c : words[i]){
: p.first[c - 'a']++;
: flag |= p.first[c - 'a'] > abc[c - 'a'];
: p.second += score[c - 'a'];
: }
: if(flag)
: continue;
: if(!st.count(p.first)){
: dp.push_back(p);
: st.emplace(p.first);
: if(p.second > ans){
: ans = p.second;
: s = p.first;
: }
: }
: }
: }
: return ans;
: }
: };
思路:
先用兩個字典紀錄字母的數量與分數
之後backtracking
Python Code:
class Solution:
def maxScoreWords(self, words: List[str], letters: List[str], score:
List[int]) -> int:
mp1 = defaultdict(int)
mp2 = defaultdict(int)
for c in letters:
mp1[c] += 1
for i in range(len(score)):
mp2[chr(97 + i)] = score[i]
def backtrack(state, start, mp1, mp2):
nonlocal res
for i in range(start, len(words)):
original_mp1 = mp1.copy()
tmp = 0
valid = True
for c in words[i]:
if mp1[c] > 0:
mp1[c] -= 1
tmp += mp2[c]
else:
valid = False
break
if valid:
state += tmp
backtrack(state, i + 1, mp1, mp2)
state -= tmp
mp1 = original_mp1
res = max(res, state)
res = 0
backtrack(0, 0, mp1, mp2)
return res
第一次hard寫那麼順 爽
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.171.227 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716540528.A.7C9.html