Coding Interview Prep · レッスン

Word Breakと文字列の分割

Q: 「Word Breakと文字列の分割」レッスンは無料ですか？

はい。「Word Breakと文字列の分割」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

Q: Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

Q: 「Word Breakと文字列の分割」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

Q: このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

1次元DPテーブルで、文字列を辞書の単語に分割できるか判定し、O(n²)の時間計算量とtrieによる高速化の理由を分析します。

「Word Breakと文字列の分割」はCoddyKit上の無料Coding Interview Prepレッスンです。これはレッスン3/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

Word Break 問題

Word Break（LeetCode 139）では、文字列 s と単語の辞書が与えられたとき、s を辞書にある1つ以上の単語からなる、空白で区切られた列に分割できるかどうかを判定します。たとえば、s = 'leetcode'、wordDict = ['leet', 'code'] の場合、'leet' + 'code' = 'leetcode' なので答えは True です。これは典型的な1次元DPの問題です。

s = 'leetcode'
word_set = {'leet', 'code'}
# Can we split 'leetcode' into words from word_set?
# 'leet' in set → yes, 'code' in set → yes
# So: 'leetcode' = 'leet' + 'code' → True

s2 = 'catsandog'
word_set2 = {'cats', 'dog', 'sand', 'and', 'cat'}
# No matter how we split, last part 'og' not in dict
print('Expected: True, False')

DPの定式化と状態

dp[i] は、部分文字列 s[:i] を辞書を使って分割できる場合に True になると定義します。基底条件は dp[0] = True です（空文字列は常に分割可能です）。各位置 i について、j < i を満たすすべての位置 j を確認します。dp[j] が True で、s[j:i] が辞書に含まれていれば、dp[i] = True です。最終的な答えは dp[len(s)] になります。

def word_break(s, word_dict):
    word_set = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # empty string
    
    for i in range(1, n + 1):
        for j in range(i):
            # If s[:j] is segmentable AND s[j:i] is a word
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break  # no need to check other j values
    return dp[n]

print(word_break('leetcode', ['leet', 'code']))        # True
print(word_break('catsandog', ['cats','dog','sand','and','cat']))  # False

DPテーブルをトレースする

s = 'leetcode'、辞書 {'leet', 'code'} の場合を考えます。dp[0]=T です。i=4 では、j=0、dp[0]=T であり、s[0:4]='leet' が辞書に含まれるため、dp[4]=T になります。i=8 では、j=4、dp[4]=T であり、s[4:8]='code' が辞書に含まれるため、dp[8]=T になります。単語が終わらないその他の位置は False のままです。答えが dp[8]=True であることから、文字列を分割できると確認できます。

def word_break_trace(s, word_dict):
    word_set = set(word_dict)
    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 word_set:
                dp[i] = True
                print(f'dp[{i}]=True via s[{j}:{i}]={repr(s[j:i])}')
                break
    print('dp table:', dp)
    return dp[n]

word_break_trace('leetcode', ['leet', 'code'])

時間計算量の分析

素朴なDPの時間計算量は O(n²) です。外側のループを n 回実行し、内側のループを最大 n 回実行するためです。ただし、s[j:i] のスライスにも O(n) のコストがかかるため、Pythonでの実際の計算量は O(n³) になります。1つの最適化として、辞書内の単語を走査し、各単語が位置 i で終わるかを確認する方法があります。この場合、W を辞書のサイズ、L を単語の平均長とすると、計算量は O(n × W × L) になります。面接で想定される入力の多くでは、O(n²) または O(n³) で許容されます。

# Slightly faster: iterate over words rather than all j positions
def word_break_v2(s, word_dict):
    word_set = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for word in word_set:
            wl = len(word)
            # Does 'word' end exactly at position i?
            if i >= wl and dp[i - wl] and s[i - wl:i] == word:
                dp[i] = True
                break
    return dp[n]

print(word_break_v2('applepenapple', ['apple', 'pen']))  # True

メモ化再帰による別解

同じ問題は、メモ化を使ったトップダウン方式でも解決できます。can_break(start) という再帰関数を定義し、s[start:] を分割できる場合に True を返すようにします。s[start:] の接頭辞として各単語を試し、残りの部分に対して再帰します。同じ開始位置を何度も調べ直さないよう、結果をキャッシュします。これはボトムアップDPと同等ですが、多くの位置が早い段階で枝刈りされる場合は、実際にはより高速になることがあります。

from functools import lru_cache

def word_break_memo(s, word_dict):
    word_set = set(word_dict)
    
    @lru_cache(maxsize=None)
    def can_break(start):
        if start == len(s): return True
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in word_set and can_break(end):
                return True
        return False
    
    return can_break(0)

print(word_break_memo('leetcode', ['leet', 'code']))  # True
print(word_break_memo('catsandog', ['cats','dog','sand','and','cat']))  # False

有効な分割をすべて返す

Word Break II（LeetCode 140）では、可能なすべての分割を求めます。方法はメモ化付きのバックトラッキングです。各位置から再帰し、単語が一致したら残りの部分に対して再帰します。すべての途中結果を文字列のリストとして保存します。TLEを避けるため、各開始位置から作れる文のリストをメモ化します。文の数は最悪の場合に指数関数的に増える可能性がありますが、メモ化によって重複した計算を排除できます。

from functools import lru_cache

def word_break_ii(s, word_dict):
    word_set = set(word_dict)
    
    @lru_cache(maxsize=None)
    def break_from(start):
        if start == len(s): return ['']
        results = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in word_set:
                for rest in break_from(end):
                    results.append(word if not rest else word + ' ' + rest)
        return results
    
    return break_from(0)

print(word_break_ii('catsanddog', ['cat','cats','and','sand','dog']))
# ['cat sand dog', 'cats and dog']

Trieによる最適化

辞書が大きい場合や単語が長い場合、すべての j について s[j:i] in word_set を確認すると、Pythonの文字列ハッシュ化によって遅くなります。Trieを使うと、文字ごとにTrieをたどり、実現不可能な経路を早い段階で枝刈りできます。すべての O(n) 個の開始位置を確認する代わりに、Trieに存在する経路だけをたどります。有効な単語につながる接頭辞が少ない場合、実際の実行時間を大幅に短縮できます。

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def build_trie(words):
    root = TrieNode()
    for word in words:
        node = root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True
    return root

def word_break_trie(s, word_dict):
    root = build_trie(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(n):
        if not dp[i]: continue
        node = root
        for j in range(i, n):
            ch = s[j]
            if ch not in node.children: break
            node = node.children[ch]
            if node.is_end:
                dp[j + 1] = True
    return dp[n]

print(word_break_trie('leetcode', ['leet', 'code']))  # True

境界ケースと制約

重要な境界ケースは次のとおりです。(1) 空文字列：空文字列は自明に分割可能なので、True を返します。(2) 辞書にない単語：DPは対応する位置を True に設定せず、正しく False を返します。(3) 重なり合う単語：たとえば、辞書に 'a' と 'aa' があり、s='aaa' の場合、すべての j の値を確認することでDPが自然に処理します。(4) 同じ文字の繰り返し：s='aaaaab'、dict=['a','aa','aaa'] の場合、経路は指数関数的に増えますが、メモ化によって O(n²) に抑えられます。

def word_break(s, word_dict):
    word_set = set(word_dict)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[len(s)]

# Edge cases
print(word_break('', ['hello']))          # True (empty string)
print(word_break('a', ['b']))             # False
print(word_break('aaa', ['a', 'aa']))     # True (many ways)

文字列分割への一般化

Word Break は、あらゆる文字列分割問題に一般化できます。つまり、文字列 s を何らかの規則に従って分割できるか、という問題です。辞書検索を、O(1) または O(L) で判定できる任意のチェックに置き換えます。たとえば、s を回文に分割できるかを判定する場合は、単語集合の代わりに、あらかじめ計算した回文テーブルを使います。DPの構造は同じで、変わるのは有効性のチェックだけです。

def palindrome_partition_possible(s):
    '''Can s be partitioned into palindromes? (Always yes — single chars are palindromes)'''
    n = len(s)
    # Precompute palindrome table
    is_pal = [[False]*n for _ in range(n)]
    for i in range(n): is_pal[i][i] = True
    for i in range(n-1): is_pal[i][i+1] = (s[i]==s[i+1])
    for length in range(3, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            is_pal[i][j] = s[i]==s[j] and is_pal[i+1][j-1]
    # DP similar to word break
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and is_pal[j][i-1]:
                dp[i] = True
                break
    return dp[n]

print(palindrome_partition_possible('aab'))  # True (a,a,b or aa,b)

DPとBFSのアプローチ

Word Break はBFSによる最短経路問題として捉えることもできます。文字列内の各位置をノードとし、s[j:i] が辞書に含まれている場合に、j から i へのエッジがあると考えます。ノード 0 からBFSを行い、ノード n に到達できるかを判定します。BFSの計算量も O(n² × L) ですが、面接でグラフ問題としてモデル化する場合はこちらのほうが直感的かもしれません。

from collections import deque

def word_break_bfs(s, word_dict):
    word_set = set(word_dict)
    n = len(s)
    visited = set()
    queue = deque([0])
    while queue:
        start = queue.popleft()
        if start == n: return True
        for end in range(start + 1, n + 1):
            if end not in visited and s[start:end] in word_set:
                visited.add(end)
                queue.append(end)
    return False

print(word_break_bfs('leetcode', ['leet', 'code']))    # True
print(word_break_bfs('catsandog', ['cats','dog','and','sand','cat']))  # False

面接での説明戦略

面接では、次の思考過程に沿って説明してください。(1) 各位置での選択が、それ以前に到達可能だった位置に依存していることに気づきます。これはDPの संकेतです。(2) 状態を定義します：dp[i] = s[:i] を分割できるか。(3) コーディングする前に、漸化式と基底条件を示します。(4) まず O(n²) の解法を実装し、その後の発展としてTrieによる最適化に触れます。(5) 空文字列、1文字の文字列、辞書にない単語などの境界ケースについて説明します。

# Clean final solution to present in interview
def word_break(s, word_dict):
    '''O(n^2 * L) time, O(n + W) space where W = total word length in dict'''
    word_set = set(word_dict)   # O(W) space
    n = len(s)
    dp = [False] * (n + 1)     # O(n) space
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):     # try all split points
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[n]

# Time: O(n^2 * L) - n^2 pairs, each dict lookup is O(L)
# Space: O(n) for dp array, O(W) for word_set
print(word_break('applepenapple', ['apple', 'pen']))  # True

クイックチェック

このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認します。

レッスンのまとめ

このレッスンでは、dp[i] は s[:i] を辞書の単語に分割できるかどうかを表すこと、O(n²) の漸化式では dp[j]=True かつ s[j:i] が単語集合に含まれるすべての分割位置 j を確認すること、Trieによって存在しない接頭辞を早期に枝刈りし、内側のループを高速化できることを学びました。次は、Decode Ways と経路の数え上げという、フィボナッチ数列に似た別の1次元DPパターンを扱います。

よくある質問