主題

LeetCode - 893. Groups of Special-Equivalent Strings 解題心得

Not In My Back Yard | 2021-02-07 00:00:09 | 巴幣 0 | 人氣 35

題目連結:


題目意譯:
給定你一個字串陣列 A 。

一個操作作用於 S 上,其由交換任意兩個 S 中是偶數索引值的字母或是任意兩個 S 中是奇數索引值之字母。

兩個字串 S 和 T 為特殊等價,如果存在任意步數的操作於 S 上,使得 S 等於 T。

例如, S = "zzxy" 及 T = "xyzz" 為特殊等價因為我們可以作出操作 "zzxy" -> "xzzy" -> "xyzz" ,其為交換 S[0] 和 S[2] 然後交換 S[1] 和 S[3]。

現在定義一個 A 裡的特殊等價之群組為 A 的一個非空子集合,其滿足:
該群組裡的每個字串兩兩為特殊等價、
群組大小盡可能地大(即不存在一個字串 S ,其不在群組裡但卻與該群組的每個字串特殊等價)


回傳 A 的特殊等價群組之數量。

注:
1 ≦ A.length ≦ 1000
1 ≦ A[i].length ≦ 20
所有 A[i] 的長度一樣。
所有 A[i] 只由小寫字母組成。



範例測資:
範例 1:
輸入: ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
輸出: 3
解釋:
其中一個群組為 ["abcd", "cdab", "cbad"],因為它們之間兩兩都是特殊等價,且沒有其他的字串與它們兩兩特殊等價。其他兩個群組為 ["xyzz", "zzxy"] 和 ["zzyx"] 。值得注意的是, "zzxy" 與 "zzyx" 並非特殊等價。

範例 2:
輸入: ["abc","acb","bac","bca","cab","cba"]
輸出: 3


解題思維:
用類似這題的做法,將 S 的每個字串都先變為最小表示法(Minimum Representation)——當然,只能使用題目定義的操作。所以可以將每個字串奇數、偶數索引值的字母分開,排序後再重組回去。

接著利用雜湊表(Hash Table)統計 S 裡有多少不同的最小表示法,而每種最小表示法即代表著一個群組,因此種類個數即是所求。




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

創作回應

更多創作