Java - DP tracks the words and DFS build the sentences.


  • 0
    J

    public class Solution {

    public List<String> wordBreak(String s, Set<String> wordDict) {
        @SuppressWarnings("unchecked")
    	List<String>[] dp = new ArrayList[s.length() + 1];
        dp[0] = new ArrayList<String>();
        for (int i = 0; i < s.length(); i++) {
    		for (int k = 0; k <= i; k++) {
    			String ss = s.substring(k, i + 1);
    			if (dp[k] != null && wordDict.contains(ss)) {
    				if (dp[i+1] == null) {
    					dp[i+1] = new ArrayList<String>();
    				}
    				dp[i+1].add(ss);
     			}
    		}
        }
        List<String> sentences = new ArrayList<String>();
        if (dp[dp.length - 1] == null)
        	return sentences;
        	
        List<String> temp = new ArrayList<String>();
        dfsBuildSentences(dp, dp.length - 1, sentences, temp);
        return sentences;
    }
    
    private void dfsBuildSentences(List<String>[] dp, int hi, List<String> sentences, List<String> temp) {
    	if (hi <= 0) {
    		String sentence = temp.get(temp.size() - 1);
    		int i = temp.size() - 2;
    		while (i >= 0) {
    			sentence += (" " + temp.get(i));
    			i--;
    		}
    		sentences.add(sentence);
    		
    	} else {
    		for (String word: dp[hi]) {
    			temp.add(word);
    			dfsBuildSentences(dp, hi - word.length(), sentences, temp);
    			temp.remove(temp.size() - 1);
    		}
    	}
    }
    

    }


Log in to reply
 

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