[leetcode]Word Break II - java

跟word break 相比，该题需要输入具体的方案

步骤如下

1. 使用map，存储第k个位置之前的字符串，所有的单词划分方案

2. 修剪分支，将一些不符合完全划分的单词除去

3. 遍历，获得所有符合条件的方案

 

public class Solution {
   
   public List<String> wordBreak(String s, Set<String> dict) {
        Map<Integer, List<Integer>> pMapALL = new HashMap<Integer, List<Integer>>();
        boolean[] f = new boolean[s.length()];
        for (int i = 0; i < s.length(); i++) {
            boolean flag = false;
            if (dict.contains(s.substring(0, i + 1))) {
                put(pMapALL, i, -1);
                flag = true;
            }
            for (int j = 0; j < i; j++) {
                if (f[j] && dict.contains(s.substring(j + 1, i + 1))) {
                    put(pMapALL, i, j);
                    flag = true;
                }
            }
            if (flag) {
                f[i] = true;
            }
        }
        if (f[s.length() - 1]) {
            Map<Integer, List<Integer>> pMap = new HashMap<Integer, List<Integer>>();
            LinkedList<Integer> stack = new LinkedList<Integer>();
            stack.push(s.length()-1);
            while (!stack.isEmpty()){
                Integer node = stack.pop();
                List<Integer> children = pMapALL.get(node);
                if(children != null){
                    pMap.put(node, children);
                    for(Integer child : children){
                        stack.push(child);
                    }
                }
            }

            List<String> results = new ArrayList<String>();
            for(Integer key : pMap.keySet()){
                List<Integer> children = pMap.get(key);
                if(children.contains(-1)){
                    print(pMap, -1, key, s, new LinkedList<String>(), results);
                }
            }
            return results;
        }
        return new ArrayList<String>();
    }

    private void put(Map<Integer, List<Integer>> pMap, Integer key, Integer value) {
        if (pMap.get(key) == null) {
            pMap.put(key, new ArrayList<Integer>());
        }
        pMap.get(key).add(value);
    }
    private void print(Map<Integer, List<Integer>> pMap, Integer startIndex, Integer endIndex, String s, LinkedList<String> stack, List<String> results) {
        String word = s.substring(startIndex+1, endIndex+1);
        stack.push(word);
        if(endIndex == s.length()-1){
            StringBuilder words = new StringBuilder();
           for(int i=stack.size()-1; i>=0; i--){
                words.append(stack.get(i));
               if(i != 0){
                   words.append(" ");
               }
           }
            results.add(words.toString());
            return;
        }
        for(Integer key : pMap.keySet()){
            List<Integer> children = pMap.get(key);
            for(Integer child : children){
                if(child.equals(endIndex)){
                    print(pMap, child, key, s, stack, results);
                    stack.pop();
                }
            }
        }
    }
}