単語分割可能か (Word Break)
単語分割可能か (Word Break)
このレッスンで分かること
- 文字列 DP は、「どこで切れるか」 表 1 本で表現する 感覚が重要
- 素朴な再帰では指数時間になりますが、動的計画法 で
O(n^2)あるいは辞書をset化すればO(n * m)(mは最大単語長) で解けます- Word Break 問題 は、与えられた文字列
sを、辞書wordDictにある単語の連結だけで表現できるかを判定する問題です
単語分割可能か とは
辞書にある単語の連結で対象文字列を構成できるかを判定する Word Break 問題を、DP で線形時間に近い計算量で解きます。
Word Break 問題 は、与えられた文字列 s を、辞書 wordDict にある単語の連結だけで表現できるかを判定する問題です。例えば s = "leetcode"、wordDict = ["leet", "code"] のときは True (leet + code で分割できる)。一方、s = "applepenapple"、wordDict = ["apple", "pen"] も True (apple + pen + apple) です。s = "catsandog"、wordDict = ["cats", "dog", "sand", "and", "cat"] は False で、最後に og が辞書にないため分割できません。
素朴な再帰では指数時間になりますが、動的計画法 で O(n^2) あるいは辞書を set 化すれば O(n * m) (m は最大単語長) で解けます。文字列処理 DP の入門問題としてとても良い練習です。
Word Break は 「ここで切れるか」 を表 1 本で管理する 文字列 DP の典型。検索エンジンの形態素解析にも通じる発想。
状態の定義
dp[i] を「s の最初の i 文字が分割可能か (boolean)」と定義します。境界条件は dp[0] = True (空文字列は分割済みとみなす) です。
遷移は、すべての j < i について dp[j] == True かつ s[j:i] が wordDict に含まれていれば dp[i] = True です。1 つでも見つかれば true なので、ループ中で break して構いません。
プレーンテキスト
dp[i] = True
if any j < i such that dp[j] is True and s[j:i] in wordDict図解
図のポイント (テキスト併記)
- 左端から順番に「ここまで分割できる印」を立てていき、最後に
dp[n]を見れば答えがわかります
左端から順番に「ここまで分割できる印」を立てていき、最後に dp[n] を見れば答えがわかります。
Python 実装
Python
def wordBreak(s, wordDict):
wordSet = set(wordDict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in wordSet:
dp[i] = True
break
return dp[n]ポイントは 辞書を set に変換 することです。これにより in 判定が O(1) になり、全体の計算量が落ちます。
JavaScript 実装
JavaScript
function wordBreak(s, wordDict) {
const wordSet = new Set(wordDict);
const n = s.length;
const dp = new Array(n + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && wordSet.has(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}JS では Set を使い、has で O(1) 判定します。s.substring(j, i) で部分文字列を取り出して照合します。
よくある間違い
1 つ目は 辞書を配列のまま in / includes で線形検索 してしまい、計算量が O(n^3) 以上になるケース。必ず set 化します。2 つ目は dp[0] = True の初期化忘れ。空文字列を分割済みとして扱うことが、漸化式の起点になります。3 つ目は 境界 i の範囲ミス。dp の長さは n + 1 で、最終的に返すのは dp[n] です。dp[n - 1] を返してしまうと、最後の 1 文字を見落とします。
計算量の話
s の長さ n、最大単語長 m とすると、二重ループは O(n^2)、各反復で部分文字列を切り出すのに O(m) かかります。よって合計は O(n^2 * m) 程度です。最大単語長を超える j はスキップする最適化を入れると、O(n * m^2) 程度まで落とせます。
文字列処理の DP では、部分文字列の切り出しコスト も計算量に含めて見積もる必要がある。Python の
s[j:i]はO(i - j)。
やってみよう
s = "pineapplepenapple"、辞書["apple", "pen", "applepen", "pine", "pineapple"]でTrueになることを確認する。s = "aaaaaaa"、辞書["aaaa", "aaa"]の答えも考える。True(aaa + aaaaまたはaaaa + aaa)。- 分割の すべての組合せ を返す拡張問題 (Word Break II) にも挑戦する。再帰 + メモ化が定石。
文字列 DP は、「どこで切れるか」 表 1 本で表現する 感覚が重要。Word Break で身につけたら、回文分割や正規表現マッチも解けるようになる。
よくある質問
Q. この内容は面接でよく聞かれますか？
A. コーディング面接の頻出範囲です。データ構造（リンクリスト・ツリー・グラフ）とアルゴリズム（DP・BFS/DFS）は IT 系大手の選考でほぼ確実に問われます。LeetCode の Top 100 にも該当問題が多数含まれます。
Q. 計算量と空間計算量はどっちを優先しますか？
A. 通常は時間計算量を優先し、空間が制約条件として明示されたら空間も考慮します。例えば「O(1) 空間で」と書かれていれば in-place アルゴリズム必須です。実務では時間 vs メモリのトレードオフを意識しつつ、ボトルネックを実測してから判断します。
Q. 問題が解けないときどう取り組めば良いですか？
A. まず小さな入力（n=3 程度）で手計算し、規則性を見つけます。次にナイーブ解（O(n²) でも可）を書き、最後に最適化します。いきなり最適解を狙うと手が止まりやすいので、段階的に進めるのが定石です。
次のレッスン
次は 第6章まとめクイズ — 動的計画法 (上級) で、これまで学んだ DP の典型問題を総復習します。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 単語分割 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 単語分割 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 戻り値は分割可能か否か (boolean)
- 辞書を set / HashSet / map に変換してから判定すること (in 判定 O(1))
- dp[i] = s の最初 i 文字が分割可能か、として DP で求めること
入出力例
test-cases.txt
wordBreak("leetcode", ["leet","code"]) → true
wordBreak("applepenapple", ["apple","pen"]) → true
wordBreak("catsandog", ["cats","dog","sand","and","cat"]) → false
wordBreak("aaaaaaa", ["aaaa","aaa"]) → true
wordBreak("a", ["b"]) → false
wordBreak("ab", ["a","b"]) → true