google新题求解

Carrick 发表于 2019/12/25 11:41:46
如果将weights做成一个基本的字典树，好像就是nwl（query）+ mwl （建trie）了，w是trie每一层平...

我感觉应该是nd n是query的长度 d是trie的深度 因为在每一个位置 都是往前走 然后 其实就是一直沿着trie来走 直到走不通为止 不过worst case其实和不加trie一样

平安夜，练练手。DFS+Trie+MEMO。

1. class Trie_Node:
   
2.     def __init__(self):
   
3.         self.alphabet = {}
   
4.         self.weight = -1
   
5.    
   
6.     def add(self, s, w):
   
7.         node = self
   
8.         for c in s:
   
9.             if c not in node.alphabet:
   
10.                 node.alphabet[c] = Trie_Node()
    
11.             node = node.alphabet[c]
    
12.         node.weight = w
    
13. 
    
14. class Solution:
    
15. 
    
16.     def max_weight_divice(self, query, weights):
    
17. 
    
18.         trie = Trie_Node()
    
19.         for s, w in weights.items():
    
20.             trie.add(s, w)
    
21. 
    
22.         def dfs(inherited, query, memo):
    
23.             if not query:
    
24.                 return inherited
    
25.             if query not in memo:
    
26.                 node, max_score = trie, -1
    
27.                 for i, c in enumerate(query):
    
28.                     if c not in node.alphabet:
    
29.                         break
    
30.                     node = node.alphabet[c]
    
31.                     if node.weight > -1:
    
32.                         score = dfs(node.weight, query[i+1:], memo)
    
33.                         max_score = max(max_score, score)
    
34.                 memo[query] = max_score
    
35. 
    
36.             return inherited + memo[query] if memo[query] >= 0 else -1
    
37. 
    
38.         return dfs(0, query, {})

复制代码

我來拋磚引玉 發個Python的 DFS+memo 代碼吧 測試了一下應該沒錯

class Solution:
    def func(self, string, weights):
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def dfs(index, count):
            if index >= len(string):
                return 0
            
            res = 0
            for i in range(index+1, len(string)+1):
                temp = string[index:i]
                if temp in weights:
                   res = max(res, weights[temp] + dfs(i, count + weights[temp]))
            
            return res
        
        return dfs(0, 0)
   

s = Solution()
string = "abcdefg"
weights = {"a": 1, "abc": 10, "bcd": 11, "cde": 30, "e": 3, "fg": 5}
print(s.func(string, weights))

dp naive的On3，把字符串hash之后做可以优化到On2，把字符串建立ac自动机做可以优化到on

补充内容 (2019-12-24 22:50):
ac自动机也是n2，说错了

dfs+mem，离口有类似题目

dp表示截止到第i个字符，能够得到多少分，初始值都是-1。典型的DP。

1. [/i]
   
2. [i]for (int i=0; i<n; i++)[/i]
   
3. [i] for (int j=0; j<i; j++) {[/i]
   
4. [i]    if (weight.find(str.substr(j+1,i-j)!=weight.end())[/i]
   
5. [i]      dp = max(dp[j]+weight[str.substr(j+1,i-j)]);
   
6. }
   
7. return dp[n-1];
   

复制代码

wisdompeak2 发表于 2019-12-25 15:12
dp表示截止到第i个字符，能够得到多少分，初始值都是-1。典型的DP。
[mw_shl_code=cpp,true]
for (int i= ...

weight.end()是什么意思？

类似leetcode上的一道题，给一个字符串ｓ和字典，问ｓ是否能有字典组成，这道题是顺便求最大值，动态规划
优化步骤根据字典有关：求字段字符串长度最大值和最小值
有数组a[i]为字符串从０到ｉ由字典组成的weight是多少
for(int i = 0; i < s.length(); i++) {
  for (int j=i-Min(字典字符串长度);j>=i-Max(字典字符串长度) && j>=0;j--) {
    if(字典存在(s.substring(j,i+1))) {
      max = Math.max(max, dict.get(s.substring(j+1,i+1)) + a[j]);
}
}
}


各种边界自己改下，字典本身是哈希表，找到最大值只能看所有的能构成ｓ的组合中找到最大值，只是中间重复计算存起来

朴笑玉 发表于 2019-12-26 11:03
类似leetcode上的一道题，给一个字符串ｓ和字典，问ｓ是否能有字典组成，这道题是顺便求最大值，动态规划
...

如果对求大米，需要看篇文章大米不够用，非常感谢

大概就是 WordBreak 的变形, 每个子字串有各自的分数, 求分数最大的切法

1. function query(s, weights) {
   
2.   const dp = new Array(s.length + 1).fill(-1);
   
3. 
   
4.   dp[0] = 0;
   
5.   for (let i = 1; i <= s.length; i++) {
   
6.     for (let j = 0; j < i; j++) {
   
7.       const str = s.substring(j, i);
   
8.       if (dp[j] > -1 && weights[str] !== undefined) {
   
9.         dp = Math.max(dp, dp[j] + weights[str]);
   
10.       }
    
11.     }
    
12.   }
    
13. 
    
14.   return dp[s.length];
    
15. }
    

复制代码