[Algorithm] LeetCode - Word Break

📠 문제

• Word Break
• 난이도: Medium
• 단어 사전에 있는 단어 조합으로 주어진 문자열을 모두 대체할 수 있는지 찾는 문제

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

🚧 시행착오

아래와 같이 풀면 되지 않을까? 생각했다. 앞에서부터 순회하지 않는 이유는 word, words 같은 두 개의 문자가 있을 때 words를 대체해야 하기 때문에 앞에서부터 하면 word를 하고 s가 남지 않을까? 해서였다.

func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
    var words = Set(wordDict)
    var buffer = ""

    for chr in s.reversed() {
        buffer = String(chr) + buffer

        if words.contains(buffer) {
            buffer = ""
        }
    }

    return buffer.isEmpty
}

하지만 이 풀이는 s = "aaaaaaa" wordDick = ["aaa", "aaaa"] 일때 바로 실패했다. ☠️ 왜냐하면 결국 a가 남기 때문에...!

💡 풀이

결국 이 문제는 dp로 풀게 되었다. 이전의 검증된 배열에서 추가로 단어를 더해가는 것이기 때문에 아래와 같이 dp배열을 만들어 준 뒤, 해당 길이까지 true라면 그때 이후로 단어가 들어가 있는지를 확인하는 방식이다.

func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
    var words = Set(wordDict)
    var chrs = Array(s)
    
    var dp = Array(repeating: false, count: s.count + 1)
    dp[0] = true

    for i in 1...s.count {
        for j in 0..<i {
            let word = String(chrs[j..<i])

            if dp[j] && words.contains(word) {
                dp[i] = true
                break
            }
        }
    }

    return dp[s.count]
}

살짝 아쉬운 결과가 나왔다. 뭔가 놓친 게 있는 걸까?

🔨 개선된 풀이

모든 단어의 개수보다는 사전에 있는 단어 개수로만 판단하면 되지 않을까라는 생각에 아래와 같이 wordCounts배열을 만든 뒤 이 안에 있는 값만 활용했다. 물론 longestWordCount만 찾아서 판별하는 방법도 있긴 하지만 아래의 방식이 좀 더 이해가 되는 느낌이 들어 아래와 같이 작성했다.

 

물론 여기서 sorted(by: >)로 긴 단어부터 체크하면 시간이 조금 더 빨라졌지만 그건 테스트케이스에 따라 그리고 LeetCode는 빌드할 때마다 근소한 차이가 보이기 때문에 큰 의미가 없다고 생각했다. 오히려 sorted를 해주면 O(n)이 O(nlogn)으로 늘어나기 때문에 좋지 않다고 판단했다.

func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
    var words = Set(wordDict)
    var wordCounts = words.map { $0.count }
    var chrs = Array(s)
    
    var dp = Array(repeating: false, count: s.count + 1)
    dp[0] = true

    for end in 1...s.count {
        for wordCount in wordCounts {
            let start = max(end - wordCount, 0)

            let word = String(chrs[start..<end])

            if dp[start] && words.contains(word) {
                dp[end] = true
                break
            }
        }
    }

    return dp[s.count]
}

9ms로 만족할 만한 결과가 나왔다. 돌릴 때마다 2~3ms는 편차가 있는 듯하다.