Swift solution - HashTable


  • 0
    class Solution {
        func findDuplicate(_ paths: [String]) -> [[String]] {
            if paths.count == 0 {
                return []
            }
            
            let fileMap = constructFileMap(paths)
            let result = duplicateFilePath(fileMap)
            
            return result
        }
        
        private func constructFileMap(_ paths: [String]) -> [String: Set<String>] {
            var fileMap = [String: Set<String>]()
            
            for path in paths {
                let items = path.components(separatedBy: " ")
                let directory = items[0]
                for i in 1..<items.count {
                    let item = items[i]
                    if let range1 = item.range(of: "("),
                        let range2 = item.range(of: ")") {
                        let fileName = item.substring(to: range1.lowerBound)
                        let content = item.substring(with: range1.upperBound..<range2.lowerBound)
                        let fullFileName = directory + "/" + fileName
                        if fileMap[content] == nil {
                            fileMap[content] = Set<String>()
                        }
                        fileMap[content]?.insert(fullFileName)
                    }
                }
            }
            
            return fileMap
        }
        
        private func duplicateFilePath(_ fileMap: [String: Set<String>]) -> [[String]] {
            var duplicates = [[String]]()
            
            for value in fileMap.values {
                if value.count >= 2 {
                    duplicates.append(Array(value))
                }
            }
    
            return duplicates
        }
    }
    

  • 0
    T

    @cloud.runner My solution is similar to yours, but it shows "Time Limit Exceeded" on extreme large test. It seems that it's due to Swift's implementation of String type, and I have to use another language to pass this question :(


  • 0
    I

    @cloud.runner said in Swift solution - HashTable:

    class Solution {
    func findDuplicate(_ paths: [String]) -> [[String]] {
    if paths.count == 0 {
    return []
    }

        let fileMap = constructFileMap(paths)
        let result = duplicateFilePath(fileMap)
        
        return result
    }
    
    private func constructFileMap(_ paths: [String]) -> [String: Set<String>] {
        var fileMap = [String: Set<String>]()
        
        for path in paths {
            let items = path.components(separatedBy: " ")
            let directory = items[0]
            for i in 1..<items.count {
                let item = items[i]
                if let range1 = item.range(of: "("),
                    let range2 = item.range(of: ")") {
                    let fileName = item.substring(to: range1.lowerBound)
                    let content = item.substring(with: range1.upperBound..<range2.lowerBound)
                    let fullFileName = directory + "/" + fileName
                    if fileMap[content] == nil {
                        fileMap[content] = Set<String>()
                    }
                    fileMap[content]?.insert(fullFileName)
                }
            }
        }
        
        return fileMap
    }
    
    private func duplicateFilePath(_ fileMap: [String: Set<String>]) -> [[String]] {
        var duplicates = [[String]]()
        
        for value in fileMap.values {
            if value.count >= 2 {
                duplicates.append(Array(value))
            }
        }
    
        return duplicates
    }
    

    }

    submit your code , but get TLE ...


  • 1
    T

    @ivoryxiong It's the fault of the Swift's String type implementation. I wrote it in Python3 and got AC(225ms) at once using the same algorithm. And I don't think it's a good idea to use Swift in those "string problems" now, maybe it would get better in later Swift release versions.


  • 0
    I

    @tatowilson thx, I start to use Java for String problems :(


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.