ETH官方钱包

前往
大廳
主題

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

Not In My Back Yard | 2021-10-26 00:00:05 | 巴幣 0 | 人氣 300

題目連結:


題目意譯:
給定兩個等長之字串 s 和 t。在一次步驟之中你可以選擇 t 的任一字元並將其替換為另一字元。

回傳將 t 變為 s 的一個易位構詞(Anagram)所需的最少步驟數。

一個字串的易位構詞為一字串其包含同樣的字元但有著不同(或是相同)的順序。

限制:
1 ≦ s.length ≦ 50000
s.length == t.length
s 和 t 只包含小寫英文字母。



範例測資:
範例 1:
輸入: s = "bab", t = "aba"
輸出: 1
解釋: 將 t 中第一個 'a' 替換 b,t = "bba" 其為 s 的易位構詞。

範例 2:
輸入: s = "leetcode", t = "practice"
輸出: 5
解釋: 將 t 中的 'p' 、 'r' 、 'a' 、 'i' 和 'c' 替換成適合的字元使得 t 為 s 的易位構詞。

範例 3:
輸入: s = "anagram", t = "mangaar"
輸出: 0
解釋: "anagram" 和 "mangaar" 互為易位構詞。

範例 4:
輸入: s = "xxyyzz", t = "xxyyzz"
輸出: 0

範例 5:
輸入: s = "friend", t = "family"
輸出: 4


解題思維:
統計 s 和 t 各自的字元出現情況並將相同的字元之出現次數互相抵銷。然後將抵銷後的字元之總字元數加總。然後將總和除以 2 即是所求(因為兩者的字元差別數就是所求)。




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

創作回應

更多創作