> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/101-200/word-break-ii.md).

# 140. Word Break II

### Description

Given a **non-empty** string *s* and a dictionary *wordDict* containing a list of **non-empty** words, add spaces in *s* to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

**Note:**

* The same word in the dictionary may be reused multiple times in the segmentation.
* You may assume the dictionary does not contain duplicate words.

### Constraints

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/word-break-ii/)
* [ProgramCreek](https://www.programcreek.com/2014/03/leetcode-word-break-ii-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** s = "catsanddog", wordDict = \["cat", "cats", "and", "sand", "dog"]

**Output:**

\[

"cats and dog",

"cat sand dog"

]
{% endtab %}

{% tab title="Example 2" %}
**Input:** s = "pineapplepenapple", wordDict = \["apple", "pen", "applepen", "pine", "pineapple"]

**Output:**

\[

"pine apple pen apple",

"pineapple pen apple",

"pine applepen apple"

]

**Explanation:** Note that you are allowed to reuse a dictionary word.
{% endtab %}

{% tab title="Example 3" %}
**Input:** s = "catsandog", wordDict = \["cats", "dog", "sand", "and", "cat"]

**Output:** \[]
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        int sLen = s.length();
        List<String> result = new ArrayList<>();
        if(sLen == 0) return result;
        
        ArrayList<String>[] pos = new ArrayList[sLen+1];
        pos[0] = new ArrayList<String>();

        for(int i = 0; i < sLen; i++) {
            if(pos[i] != null) {
                for(int j = i+1; j <= sLen; j++) {
                    String str = s.substring(i, j);
                    if(wordDict.contains(str)) {
                        if(pos[j] == null) {
                            pos[j] = new ArrayList<String>();
                        }
                        pos[j].add(str);
                    }
                }
            }
        }
        
        if(pos[sLen] == null) return result;
        
        dfs(result, pos, "", sLen);
        
        return result;
    }
    
    private void dfs(List<String> result,
                     ArrayList<String>[] pos,
                     String currStr,
                     int i) {
        if(i == 0) {
            result.add(currStr.trim());
            return;
        }
        
        for(String word: pos[i]) {
            dfs(result, pos, word+" "+currStr, i-word.length());
        }
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*