前往
大廳
主題

LeetCode - 1422. Maximum Score After Splitting a String 解題心得

Not In My Back Yard | 2023-05-14 12:00:22 | 巴幣 0 | 人氣 143

題目連結:


題目意譯:
給定一個只有 0 和 1 的字串 s,回傳將字串分拆成兩個非空的子字串(即左邊的子字串以及右邊的子字串)所能得到的最大分數。

分拆一個字串後的分數為左邊的子字串裡 0 的數量加上右邊的子字串裡 1 的數量。

限制:
2 ≦ s.length ≦ 500
字串 s 只由字元 '0' 和 '1' 組成。



範例測資:
範例 1:
輸入: s = "011101"
輸出: 5
解釋:
所有可能將 s 分拆成兩個非空子字串的方式為:
left = "0" 且 right = "11101",分數 = 1 + 4 = 5
left = "01" 且 right = "1101",分數 = 1 + 3 = 4
left = "011" 且 right = "101",分數 = 1 + 2 = 3
left = "0111" 且 right = "01",分數 = 1 + 1 = 2
left = "01110" 且 right = "1",分數 = 2 + 1 = 3

範例 2:
輸入: s = "00111"
輸出: 5
解釋: 當 left = "00" 而 right = "111",我們得到最大分數 = 2 + 3 = 5

範例 3:
輸入: s = "1111"
輸出: 3


解題思維:
因為 s 的長度不長,所以直接窮舉每一種拆分方式並計算分數取出最大值即可。




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

創作回應

更多創作