前往
大廳
主題

LeetCode - 2186. Minimum Number of Steps to Make Two Strings Anagram II 解題心得

Not In My Back Yard | 2022-10-10 12:00:03 | 巴幣 0 | 人氣 154

題目連結:


題目意譯:
你被給定兩字串 s 和 t。在一步中,你可以加入任意字元到 s 或是 t 之中。

回傳使 s 和 t 互為易位構詞(Anagram)最少所需的步數。

一個字串之一個易位構詞為一字串,其包含著相同的字元且有著不同(或相同)之排列順序。

限制:
1 ≦ s.length, t.length ≦ 2 × 10 ^ 5
s 和 t 由小寫英文字母組成。



範例測資:
範例 1:
輸入: s = "leetcode", t = "coats"
輸出: 7
解釋:
- 在 2 步中,我們可以將字母 "as" 加到 s = "leetcode" 中,形成 s = "leetcodeas"。
- 在 5 步中,我們可以將字母 "leede" 加到 t = "coats",形成 t = "coatsleede"。
"leetcodeas" 和 "coatsleede" 現在互為易位構詞。
我們總共使用了 2 + 5 = 7 步。
可以證明無法在小於 7 步以內使它們變成互為易位構詞。

範例 2:
輸入: s = "night", t = "thing"
輸出: 0
解釋: 給定的字串已經互為易位構詞。因此不需要額外的步驟。


解題思維:
跟系列第一題(這題)很像,也是統計 s 和 t 出現的字母然後互相抵銷。但是這次的所需的步數因為是「添加字母」而不是「替換字母」,因此每一步只會將兩者的字母差距減少 1。因此把所有兩者抵銷後剩下的字元數加總即是所求。




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

創作回應

更多創作