[Swift 알고리즘] LeetCode 2506. Count Pairs Of Similar Strings

○

Hash Table, 조합 | Easy

2506. Count Pairs Of Similar Strings

문제 해결이 어렵진 않은데, 조합 구현 공식은 컨닝함.. ㅎㅎ 

영어가 문제인가 문제 설명이 문제인가.. 처음에 읽어보고 뭐라는건지 모르겠어서 포기할 뻔 했쟈나

이해하고 나면 간단함.

 

1. words 안의 각 문자열들을 Set으로 중복 제거하고, sort로 정렬하고 다시 문자열로 만들어준다.

2. 위의 변환 과정을 거친 문자열을 딕셔너리의 키 값으로 넣어 주고, 같은 문자열일 경우 값을 1씩 더해준다.

3. 딕셔너리에 저장된 중복 문자열로 pair 가 만들어질 수 있는 경우의 수는 nCr 이기 때문에,

조합 공식을 사용해 (n * (n -1)) / 2 로 구해준다.

import Foundation

let solution = Solution()
print(solution.similarPairs(["aba","aabb","abcd","bac","aabc"])) //2
print(solution.similarPairs(["aabb","ab","ba"])) //3

class Solution {
    func similarPairs(_ words: [String]) -> Int {
        var dict: [String:Int] = [:]
        var result = 0
        
        for word in words {
            let key = Set(word).sorted().map { String($0) }.joined()
            dict[key, default: 0] += 1
        }
        
        for (_, value) in dict {
            result += (value * (value - 1)) / 2
        }
        
        return result
    }
}