---
title: 140. Word Break II
tags: String
description: share source code.
---

# 140. Word Break II

class Solution {
    Set<String> set;
    
    public List<String> wordBreak(String s, List<String> wordDict) {
        set = new HashSet<>(wordDict);
        int n = s.length();
        Map<Integer, List<String>> map = new HashMap<>();
        List<String> output = helper(s, 0, map);
        output.removeIf(o -> o.replace(" ","").length() < n );
        
        return output;
    }
    
    public List<String> helper(String s, int idx,  Map<Integer, List<String>> map){
        int n = s.length();
        if(idx == n){
            return new ArrayList<>();
        }
        
        if(map.containsKey(idx)){
            return map.get(idx);
        }
        
        List<String> list = new ArrayList<>();
        
        for(int i = idx; i <= n; i ++){
            String str = s.substring(idx, i);
            if(set.contains(str)){
               List<String> tmp = helper(s, i, map);

               if(tmp.isEmpty()){
                   list.add(str);
               }else{
                  for(String t : tmp){
                     list.add(str+" "+ t);
                  }
               }
             
            }
        }
        
        map.put(idx, list);
        
        return  list;
    }
}