Google — Word Break II (DP + Backtracking with Memoisation)

Problem (Google Hard DP)

Given a string s and dictionary wordDict, return all ways to segment s into dictionary words.

Example:

s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
→ ["cats and dog","cat sand dog"]

Key Insight — DP + Backtracking

DP check: First verify s can be segmented at all (avoid TLE on bad inputs)
Backtrack with memo: DFS from position i, try all s[i:j] in dict. Memoize results per start index.

Solutions

Python

def wordBreak(s, wordDict):
    word_set = set(wordDict)
    memo = {}

    def backtrack(start):
        if start in memo:
            return memo[start]
        if start == len(s):
            return ['']
        res = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in word_set:
                for rest in backtrack(end):
                    res.append(word + (' ' + rest if rest else ''))
        memo[start] = res
        return res

    return backtrack(0)

JavaScript

function wordBreak(s, wordDict) {
    const ws=new Set(wordDict), memo=new Map();
    const bt=(i)=>{
        if(memo.has(i)) return memo.get(i);
        if(i===s.length){memo.set(i,['']);return [''];}
        const res=[];
        for(let j=i+1;j<=s.length;j++){
            const w=s.slice(i,j);
            if(ws.has(w)) for(const rest of bt(j)) res.push(rest?w+' '+rest:w);
        }
        memo.set(i,res); return res;
    };
    return bt(0);
}

Java

import java.util.*;
Map<Integer,List<String>> memo=new HashMap<>(); Set<String> ws;
public List<String> wordBreak(String s, List<String> dict) {
    ws=new HashSet<>(dict); return bt(s,0);
}
List<String> bt(String s, int i) {
    if(memo.containsKey(i)) return memo.get(i);
    List<String> res=new ArrayList<>();
    if(i==s.length()){res.add("");memo.put(i,res);return res;}
    for(int j=i+1;j<=s.length();j++){
        String w=s.substring(i,j);
        if(ws.contains(w)) for(String r:bt(s,j)) res.add(r.isEmpty()?w:w+" "+r);
    }
    memo.put(i,res); return res;
}

C++

#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>
using namespace std;
unordered_map<int,vector<string>> memo;
unordered_set<string> ws;
vector<string> bt(const string& s, int i) {
    if(memo.count(i)) return memo[i];
    vector<string> res;
    if(i==(int)s.size()){res.push_back("");return res;}
    for(int j=i+1;j<=(int)s.size();j++){
        string w=s.substr(i,j-i);
        if(ws.count(w)) for(auto& r:bt(s,j)) res.push_back(r.empty()?w:w+" "+r);
    }
    return memo[i]=res;
}
vector<string> wordBreak(string s, vector<string>& dict){ws={dict.begin(),dict.end()};return bt(s,0);}

C

/* C: iterative DP to find valid split points, then trace-back to build strings */