140. Word Break II

Title: 140. Word Break II

Given anon-emptystringsand a dictionarywordDictcontaining a list ofnon-emptywords, add spaces insto 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.

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:
[]

Thinking of solving problems

In fact, the solution of this problem is the same as 139. Word break. You can refer to the idea of 139. Word break https://my.oschina.net/JiamingMai/blog/4331735 , slightly different from 139. Word break, this question needs to record all the cases in which h [0] [i] is true.

Time complexity analysis

In essence, it is the same as 139. Word break, so the time complexity is O (KN ^ 2), which is a reference for the analysis process https://my.oschina.net/JiamingMai/blog/4331735

Finally realized

java implementation 

public class Solution {

    List<String&>[] records;

    private boolean[][] h;

    private boolean[][] r;

    public List<String&> wordBreak(String s, List<String&> wordDict) {
        int n = s.length();
        if (!fastWordBreakInternal(s, wordDict)) {
            return new ArrayList<&>();
        }
        boolean res = wordBreakInternal(s, wordDict);
        if (res) {
            return records[n];
        }
        return new ArrayList<&>();
    }

    public boolean fastWordBreakInternal(String s, List<String&> wordDict) {
        int n = s.length();
        h = new boolean[n+1][n+1];
        r = new boolean[n+1][n+1];
        initR(n, s, wordDict);
        h[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j &>= 0; j--) {
                if (!h[0][i]) {
                    h[0][i] = h[0][i-j] && r[i-j][i];
                } else {
                    break;
                }
            }
        }
        return h[0][n];
    }

    public boolean wordBreakInternal(String s, List<String&> wordDict) {
        int n = s.length();
        h = new boolean[n + 1][n + 1];
        r = new boolean[n + 1][n + 1];
        records = new List[n + 1];
        initR(n, s, wordDict);
        h[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j &>= 0; j--) {
                if (h[0][i - j] && r[i - j][i]) {
                    h[0][i] = true;
                    record(i, j, s);
                }
            }
        }
        return h[0][n];
    }

    private void record(int i, int j, String s) {
        if (null == records[i]) {
            records[i] = new ArrayList<&>();
        }
        String token = s.substring(i - j, i);
        if (null != records[i - j]) {
            for (String str : records[i - j]) {
                StringBuffer sb = new StringBuffer();
                sb.append(str).append(" ").append(token);
                records[i].add(sb.toString());
            }
        }  else {
            records[i].add(token);
        }
    }

    private void initR(int n, String s, List<String&> wordDict) {
        for (int i = 0; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                r[i][j] = r(i, j, s, wordDict);
            }
        }
    }

    private boolean r(int i, int j, String s, List<String&> wordDict) {
        String token = s.substring(i, j);
        for (String word : wordDict) {
            if (word.equals(token)) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        List<String&> wordDict = new ArrayList<&>();
        wordDict.add("a");
        wordDict.add("aa");
        wordDict.add("aaa");
        wordDict.add("aaaa");
        wordDict.add("aaaaa");
        wordDict.add("aaaaaa");
        wordDict.add("aaaaaaa");
        wordDict.add("aaaaaaaa");
        wordDict.add("aaaaaaaaa");
        wordDict.add("aaaaaaaaaa");
        String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        Solution solution = new Solution();
        List<String&> res = solution.wordBreak(s, wordDict);
        res.stream().forEach(str -&> {System.out.println(str);});
    }

}

note that in the main method of the code, the input is a continuous string of a with only one B in the middle. In this case, if you record while calculating directly, it will time out. So here’s a trick to quickly determine whether the input string can be disassembled. If not, you can directly output an empty list. This example is just a case that cannot be disassembled.

Similar Posts: