14. Longest Common Prefix

- 접근 방법:

 

1. 주어진 strs array를 string count에 따라 오름차순 정렬.

2. 정렬된 array의 요소들의 firstLetter를 한 번씩 확인. 모든 요소들의 first letter가 동일하면 result에 추가하고, 그렇지 않으면 return.

3. strs array의 첫번째 요소가 가장 count가 작기 때문에, 이 string의 count가 0이 되면 더 이상 확인하지 않음.

class Solution {
    func longestCommonPrefix(_ strs: [String]) -> String {
        var sortedStrs: [String] = strs.sorted { $0.count < $1.count }
        var result: String = ""
        var charSet: Set<String> = Set<String>()

        while true {
            if sortedStrs[0].count == 0 { break }

            for i in 0..<sortedStrs.count {
                var str: String = sortedStrs[i]
                let firstLetter: String = String(str.removeFirst())
                charSet.insert(firstLetter)
                sortedStrs[i] = str
            }

            if charSet.count == 1 {
                result.append(charSet.first!)
                charSet = Set<String>()

            } else {
                break
            }
            
        }

        return result
    }
}

 

통과는 했으나 코드를 작성하면서

str array를 여러 번 순회해야 한다는 부분이 효율적이지 못한 것 같았고, 조건 확인문이 조금 복잡(?)해서 실수하기 좋다는 생각이 들었다.

 

풀이 중에 깔끔한 풀이가 있었는데, strs 중 첫 번째 요소를 prefix라고 가정하고 불필요한 letter를 제거해가는 부분이 새롭게 느껴졌다.

뿐만 아니라, strs를 한 번만 순회하기 때문에 훨씬 효율적일 것이라는 생각이 든다.

 

class Solution {
    func longestCommonPrefix(_ strs: [String]) -> String {
        guard strs.count >= 1 && strs.count <= 200 else { return "" }
        guard let firstStr = strs.first else { return "" }
        
        var prefix = firstStr
        
        for str in strs {
            while !str.hasPrefix(prefix) {
                prefix.removeLast()
                if prefix.isEmpty { return "" }
            }
        }
        
        return prefix
    }
}