Java DP on Indices


  • 0
    H

    Use DP method for Word Break, but also record the "correct previous indices" for the indices come later. Then recursively build the result on the indices map.

    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> result = new ArrayList<>();
        if(s == null) return result;
        boolean[] dp = new boolean[s.length() + 1];
        Map<Integer, List<Integer>> indices = new HashMap<Integer, List<Integer>>();
        dp[0] = true;
        for(int i = 1; i < dp.length; i++){
            for(int j = i - 1; j >= 0; j--){
                if(wordDict.contains(s.substring(j, i)) && dp[j]){
                    dp[i] = true;
                    if(!indices.containsKey(i)){
                        List<Integer> before = new ArrayList<>();
                        before.add(j);
                        indices.put(i, before);
                    } else {
                        List<Integer> before = indices.get(i);
                        before.add(j);
                        indices.put(i, before);
                    }
                }
            }
        }
        if(!dp[s.length()]) return result;
        build(s.length(), indices, result, new StringBuilder(), s);
        return result;
    }
    private void build(int currentInd, Map<Integer, List<Integer>> indices, List<String> result, StringBuilder sb, String s){
        List<Integer> before = indices.get(currentInd);
        for(Integer beforeInd : before){
            if(beforeInd == 0){
                sb.insert(0, s.substring(beforeInd, currentInd));
                result.add(sb.toString());
                sb.delete(0, currentInd);
                return;
            }
            sb.insert(0, " " + s.substring(beforeInd, currentInd));
            build(beforeInd, indices, result, sb, s);
            sb.delete(0, currentInd - beforeInd + 1);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.