Java教程

140. Word Break II

本文主要是介绍140. Word Break II，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

My back tracking solution1:

class Solution {
    List<String> res = new ArrayList<>();
    Set<String> set = new HashSet<>();
    public List<String> wordBreak(String s, List<String> wordDict) {
        for(String word:wordDict){
            set.add(word);
        }
        List<String> list = new ArrayList<>();
        backTracking(s, 0, list);
        return res;
    }
    
    private void backTracking(String s, int index, List<String> list){
        if(index==s.length()){
            StringBuilder temp = new StringBuilder();
            for(String word: list){
                temp.append(word+" ");
            }
            temp.deleteCharAt(temp.length()-1);
            res.add(temp.toString());
            return;
        }
        
        for(int i=index+1;i<s.length()+1;i++){
            String word = s.substring(index,i);
            if(set.contains(word)){
                list.add(word);
                backTracking(s, i, list);
                list.remove(list.size()-1);
            }
        }
        
    }
}

 My back tracking solution2:

class Solution {
    List<String> res = new ArrayList<>();
    Set<String> set = new HashSet<>();
    public List<String> wordBreak(String s, List<String> wordDict) {
        for(String word:wordDict){
            set.add(word);
        }
        
        List<String> list = new ArrayList<>();
        backTracking(s, wordDict, list);
        return res;
    }
    
    private void backTracking(String s, List<String> wordDict, List<String> list){
        if(s.length()==0){
            StringBuilder temp = new StringBuilder();
            for(String word: list){
                temp.append(word+" ");
            }
            temp.deleteCharAt(temp.length()-1);
            res.add(temp.toString());
            return;
        }
        
        for(String word: wordDict){
            if(s.startsWith(word)){
                list.add(word);
                backTracking(s.substring(word.length()), wordDict, list);
                list.remove(list.size()-1);
            }
        }
        
    }
}

 

这篇关于140. Word Break II的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航