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

• ProgramCreek

• YouTube

Examples

Example 1

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

Output:

[

"cats and dog",

"cat sand dog"

]

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.

Example 3

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

Output: []

Solutions

Solution 1

/**
 * 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());
        }
    }
}

Follow up