[Swift] LeetCode: Longest Common Prefix (문자열)

https://leetcode.com/problems/longest-common-prefix/submissions/

Longest Common Prefix - LeetCode

 

XCode 없이 풀다가 별 문법 틀린 것 없이 한번에 success 가 떠서 대박! 했던 문제

String index 에 조금 적응한 기분 갬덩 ㅠ...ㅠ

 

문제

문제 제목 그대로 모든 문자열의 가장 긴 Prefix 접두사를 구하는 문제

 

생각

주어진 String 배열의 첫번째 문자를 기준으로 잡고 첫번째 문자의 subString (전체문자, 전체문자 - 1, 전체문자 - 2...) 을 구한 후에

hasPrefix 함수로 prefix로 가지고 있는지 확인해주었습니다.

가장 긴 문자열부터 비교하면 가장 긴 Prefix를 빨리 구할 수 있기 때문에 긴 문자열부터 비교하였습니다.

 

사담

처음에는 주어진 String 배열을 정렬한 후에 Prefix를 구할 생각을 했는데 

블로그에 글을 정리하려고 보니 굳이 정렬을 할 필요가 있을까? 해서 비교

 

정렬한 코드 + 정렬하지 않은 코드

 

테스트케이스가 랜덤으로 주어지나보다..! 비교를 할 수가 없었습니다..ㅎ

그렇다면 굳이 sort를 하지 않아도 된다는 결론

 

전체 코드

class Solution {
    func longestCommonPrefix(_ strs: [String]) -> String {
        let firstStr = strs[0]
        var count = 0
        
        for i in stride(from: firstStr.count, through: 0, by: -1) {
            let firstIndex = firstStr.index(firstStr.startIndex, offsetBy: 0)
            let endIndex = firstStr.index(firstStr.startIndex, offsetBy: i)
            count = 0
            
            for str in strs {
                if str.hasPrefix(String(firstStr[firstIndex..<endIndex])) {
                   count += 1
                }
            }
            
            if count == strs.count {
                return String(firstStr[firstIndex..<endIndex])
            }
        }
        
        return ""
    }
}

 

 

오늘도 어김없이 잘 푼 사람들의 코드를 보며 생각에 빠져봅시다.

class Solution {
    func longestCommonPrefix(_ strs: [String]) -> String {
        
        if strs.isEmpty { return "" }
        var common = strs[0]
        
        for ch in strs {
            while !ch.hasPrefix(common) {
                common = String(common.dropLast())
            }
        }
        return common
    }
}

첫번째 문자열을 기준으로 잡은 풀이는 비슷합니다만

dropLast() 라는 함수를 사용하여 count 변수를 사용하지 않아도 자른 문자열을 사용가능!

 

오늘도 새로운 함수

func dropLast(_ k: Int) -> Substring

Returns a subsequence containing all but the specified number of final elements.

k 갯수만큼 끝에서 버리고 반환하는 함수입니다.

k 는 0보다 크거나 같아야합니다.

 

dropFirst() 함수도 마찬가지

func dropFirst(_ k: Int = 1) -> Substring

 다른 점은 k 가 default 1로 설정되어있습니다.