前往
大廳
主題

LeetCode - 2606. Find the Substring With Maximum Cost 解題心得

Not In My Back Yard | 2024-05-30 12:00:05 | 巴幣 0 | 人氣 113

題目連結:


題目意譯:
你被給定一個字串 s、一個字元彼此相異的字串 chars 以及一個長度與 chars 相同的整數陣列 vals。

子字串的成本為該子字串中的字元所對應的數值之總和。一個空字串的成本視為 0。

每個字元所對應的數值定義如下:
    如果字元不存在於字串 chars 中,則其對應數值為其在字母表中的對應位置(索引值從 1 開始)。
        例如說,'a' 的數值為 1 、 'b' 的數值為 2 …… 、 'z' 的數值為 26。
    否則,假設該字元出現於字串 chars 中索引值 i 這個位置,則其數值為 vals[i]。

回傳字串 s 所有子字串中的最大成本值。

限制:
1 ≦ s.length ≦ 10 ^ 5
s 只由小寫英文字母組成。
1 ≦ chars.length ≦ 26
chars 由彼此相異的小寫英文字母組成。
vals.length == chars.length
-1000 ≦ vals[i] ≦ 1000



範例測資:
範例 1:
輸入: s = "adaa", chars = "d", vals = [-1000]
輸出: 2
解釋: "a" 和 "d" 的數值分別是 1 和 -1000。
有著最大成本的子字串是 "aa",其成本為 1 + 1 = 2。
可以證明 2 是最大的成本值。

範例 2:
輸入: s = "abc", chars = "abc", vals = [-1,-1,-1]
輸出: 0
解釋: "a" 、 "b" 和 "c" 的數值分別是 -1 、 -1 和 -1。
有著最大成本的子字串是空字串 "",其成本為 0。
可以證明 0 是最大的成本值。


解題思維:
本題即是求最大連續子序列和,參見此題的前半部分。而因為可以非空,所以記得考慮什麼都不取的情況。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作