609. Find Duplicate File in System (Array, Hash Table, String)

링크 - https://leetcode.com/problems/find-duplicate-file-in-system/description/

난이도 - Medium

Intuition

Hash table로 쉽게 풀 수 있는 문제이다. 문제를 잘 이해했다면 어렵지 않을 것이다.

1. 먼저 각 path를 " "로 split한다. 첫번째 원소를 directory로 놓고 다음 원소들부터 file_path와 content로 나눠 content를 key, directory + "/" + file_path를 value로 append한다.

2. 각 hash table 아이템들을 돌면서 value의 크기가 1 이상인 것들만 ans에 append한다.

Code

class Solution:
    def findDuplicate(self, paths: List[str]) -> List[List[str]]:
        hash_table = defaultdict(list)

        for path in paths:
            p = path.split(" ")
            directory = p[0]
            for f in p[1:]:
                file_path, content = f.split("(")
                content = content[:-1]
                hash_table[content].append(directory + "/" + file_path)

        ans = []
        for k, v in hash_table.items():
            if len(v) > 1:
                ans.append(v)
        return ans

Complexity

Time Complexity: O(N*X) N은 paths의 원소의 개수이고 X는 각 string의 평균 길이이다.

Space Complexity: O(N*X) 해시 테이블의 크기는 N * X만큼 늘어나게 된다.