90.97% Java Solution with explanation


  • 0
    D

    90.97% Java Solution with explanation, please go to my blog for detail explanation.

    public class Solution {
        public boolean[] wordBreak1(String s, Set<String> wordDict) {
            boolean[] wordBreakDp = new boolean[s.length() + 1];
            if(s == null) {
                return wordBreakDp;
            }
            wordBreakDp[0] = true;
            for(int i = 1; i <= s.length(); i++) {
                for(int j = 0; j < i; j++) {
                    String word = s.substring(j, i);
                    if(wordBreakDp[j] && wordDict.contains(word)) {
                        wordBreakDp[i] = true;
                        break;
                    }
                }
            }//end for i
            return wordBreakDp;
        }
        
        public List<String> wordBreak(String s, Set<String> wordDict) {
            List<String> words = new LinkedList<>();
            boolean[] canBeBreaked = wordBreak1(s, wordDict);
            
            if(canBeBreaked[s.length()] == false) {
                return words;
            }
            
            breakToWords(s, 0, wordDict, canBeBreaked, new StringBuilder(), words);
            return words;
        }
        
        void breakToWords(String s, int start, Set<String> wordDict, boolean[] canBeBreaked, StringBuilder aWordString, List<String> words) {
            
            if(start >= s.length()) {
                words.add(aWordString.toString());
                return;
            }
            
            int nextIdx = start;
            
            while(nextIdx < s.length()) {
                if(canBeBreaked[nextIdx + 1] == false) {
                    nextIdx++;
                    continue;
                }
                //until it is can be breaked into a word
                String word = s.substring(start, nextIdx + 1);
                if(!wordDict.contains(word)) {
                    nextIdx++;
                    continue;
                }
                
                int len = aWordString.length();
                if(aWordString.length() == 0) {
                    aWordString.append(word);
                }
                else {
                    aWordString.append(" " + word);
                }
                
                breakToWords(s, nextIdx + 1, wordDict, canBeBreaked, aWordString, words);
                
                aWordString.setLength(len);
                nextIdx++;
            }
        }
    }
    

  • 0
    S
    This post is deleted!

Log in to reply
 

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