Word Break

 

문제

https://leetcode.com/problems/word-break/description/

입력

1 <= s.length <= 300 // 주어진 문장 길이 
1 <= wordDict.length <= 1000 // 단어 개수
1 <= wordDict[i].length <= 20 // 단어 길이

결과

ans: Bool = wordDict를 이용해서 s를 만들 수 있는가

해석

cache[i] = i번째 단어에 도달할 수 있는가를 판단한다.

cache[i]가 true면 wordDict에 있는 단어를 하나씩 돌면서 맞는게 있는지 비교

코드

import Foundation

extension String {
    subscript(_ range: Range<Int>) -> String {
        let startIndex = self.startIndex
        let from = self.index(startIndex, offsetBy: range.startIndex)
        let to = self.index(startIndex, offsetBy: range.endIndex)
        return String(self[from..<to])
    }
}

class Solution {
    func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
        if s.isEmpty {
            return true 
        }
     
        let n = s.count 
        var cache: [Bool] = [Bool](repeating: false, count: n+1)
        cache[0] = true 
        
        for i in 0...n {
            if !cache[i] { continue }
            for word in wordDict {
                let len = word.count
                let j = i+len
                if j <= n && s[i..<j] == word {
                    cache[j] = true
                }
            }
        }

        return cache[n]
    }
}