Word Break e segmentazione delle stringhe

Il problema Word Break

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')

Formulazione e stato della DP

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

Esecuzione passo per passo della tabella DP

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'])

Analisi della complessità temporale

# 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

Alternativa: ricorsione con memoizzazione

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

Restituire tutte le segmentazioni valide

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']

Ottimizzazione con 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

Casi limite e vincoli

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)

Generalizzazione della segmentazione di stringhe

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)

Approccio DP vs BFS

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

Strategia di comunicazione durante il colloquio

# 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

Verifica rapida

Riepilogo della lezione