題目連結:
題目意譯:
兩個字串,X 和 Y,如果兩字串一模一樣又或我們可以把字串 X 中的最多兩個字母交換(兩者位置不同)來使兩字串相等,則兩字串視為是「相似的」。
例如說,"tars" 和 "rats" 是相似的(將位置 0 和位置 2 的字母交換),且 "rats" 和 "arts" 也是相似的;但是 "star" 和 "tars" 、 "rats" 又或是 "arts" 都不相似。
組合在一起,這些字詞根據(jù)相似性形成了兩個相連群體:{"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)便可以知道有多少個群體,即為所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。