39. Word Break

読了目安約1分

DP / LeetCode 139 (Medium) — 文字列を辞書の単語の連結に分割できるか判定する DP。

この章の目次

問題

LeetCode 139. Word Break（Medium / カテゴリ: DP）

文字列 s と単語のリスト wordDict が与えられます。 s を辞書の単語だけの連結として分割できるかを判定してください。同じ単語は何回使ってもかまいません。

考え方

ヒント 1

状態を dp[i] = 「s の先頭 i 文字を単語に分割できるか」の Bool と定めます。答えは dp[s.count] です。

ヒント 2

先頭 i 文字の末尾がある単語 w に一致し、その手前 dp[i - w.count] が true なら dp[i] = true です。各 i について辞書のすべての単語を試します。初期条件は dp[0] = true（空文字列は分割済みとみなす）です。

Swift 実装のポイント

Swift の String は整数の添字で切り出せません。最初に Array(s) で [Character] に変換します。
辞書の単語も wordDict.map { Array($0) } で [Character] にそろえておきます。
部分列の比較は chars[range].elementsEqual(w) を使うと、コピーを作らずに済みます。

模範解答

Swift
class Solution {
    func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
        let chars = Array(s)
        let words = wordDict.map { Array($0) }
        let n = chars.count
        var dp = [Bool](repeating: false, count: n + 1)
        dp[0] = true
        for i in 1...n {
            for w in words where w.count <= i && dp[i - w.count] {
                if chars[(i - w.count)..<i].elementsEqual(w) {
                    dp[i] = true
                    break
                }
            }
        }
        return dp[n]
    }
}

計算量: O(N × D × L)。N は s の長さ、D は単語数、L は単語の最大長です。