My DP + DFS solution


  • 1
    Y

    Could anyone tell me why Set has been changed to List?
    //updated version 2017/01/04
    //my solution used separate DP and DFS steps
    public class Solution {

    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>();
        for(String word : wordDict){
            set.add(word);
        }
        List<String> result = new ArrayList<>();
        List<List<Integer>> record = new ArrayList<>();
        for(int i = 0; i <= s.length(); i++){
            record.add(new ArrayList<>());
        }
        record.get(0).add(0);
        for(int i = 1; i <= s.length(); i++){
            for(int j = 0; j < i; j++){
                if(record.get(j).size() > 0 && set.contains(s.substring(j, i))){
                    record.get(i).add(j);
                }
            }
        }
        
        backTrack(result, "", record, s, s.length());
        return result;
    }
    
    private void backTrack(List<String> result, String str, List<List<Integer>> record, String s, int pos){
        if(pos == 0){
            result.add(str.trim());
            return;
        }
        for(int subPos : record.get(pos)){
            backTrack(result, " " + s.substring(subPos, pos) + str, record, s, subPos);
        }
    }
    

    }


  • 0
    S

    I think they want you to implement Trie.


Log in to reply
 

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