前往
大廳
主題

LeetCode - 0839. Similar String Groups 解題心得

Not In My Back Yard | 2023-11-26 12:34:00 | 巴幣 0 | 人氣 68

題目連結:


題目意譯:
兩個字串,X 和 Y,如果兩字串一模一樣又或我們可以把字串 X 中的最多兩個字母交換(兩者位置不同)來使兩字串相等,則兩字串視為是「相似的」。

例如說,"tars" 和 "rats" 是相似的(將位置 0 和位置 2 的字母交換),且 "rats" 和 "arts" 也是相似的;但是 "star" 和 "tars" 、 "rats" 又或是 "arts" 都不相似。

組合在一起,這些字詞根據相似性形成了兩個相連群體:{"tars", "rats", "arts"} 和 {"star"}。注意到 "tars" 和 "arts" 即使互不相似也一樣同處於同一個群體之中。更正式說,每個群體滿足該群體中任一字詞至少與群體中另一個字詞相似。

我們被給定一個字串列表 strs,其中 strs 中每個字串都是其他字串的易位構詞(Anagram)。試問有多少個群體存在於其中?

限制:
1 ≦ strs.length ≦ 300
1 ≦ strs[i].length ≦ 300
strs[i] 只由小寫字母組成。
strs 中的字詞長度都相同且彼此互為易位構詞。



範例測資:
範例 1:
輸入: strs = ["tars","rats","arts","star"]
輸出: 2

範例 2:
輸入: strs = ["omv","ovm"]
輸出: 1


解題思維:
這題類似,不過本題的「相似」的條件是兩字串一模一樣又或是可以交換最多兩個字母後變成一樣(窮舉要交換的字母並檢查是否一樣即可)。而併查集(Union-Find Set)以前有介紹過,參見這題

然後本題是要求有多少群體,而不是擁有的元素最大者,因此直接算有多少「代表」(Representative)便可以知道有多少個群體,即為所求。




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

創作回應

更多創作