[Java] Accepted solution after new test case added


  • 1
    S

    Since new test cases are added, such as "baaa...a" and "aaa..aab", both frontward and backward dp versions will probably fail. I find suggestion from this post, which is to check whether the whole string is breakable at the very beginning.

    Short explanation for below solution.

    1. check the whole string is breakable using the solution from WordBreak I;

    2. if breakable, then using same dp logic from WordBreak. Be careful about the extra white space at the end of each sentence :)

    public class Solution {
    
        public List<String> wordBreak(String s, Set<String> wordDict) {
            int n = s.length();
    
            // check whether whole string can be broken
            if (!wordBreakOk(s, wordDict)) {
                return new ArrayList<>();
            }
    
            // initialize
            List<List<String>> dp = new ArrayList<>();
            for (int i = 0; i <= n; i++) {
                dp.add(new ArrayList<>());
            }
            dp.get(n).add("");
    
            for (int i = n - 1; i >= 0; i--) {
                for (int j = i; j <= n; j++) {
                    String word = s.substring(i, j);
                    if (wordDict.contains(word)) {
                        for (String sentence : dp.get(j)) {
                            StringBuilder sb = new StringBuilder(word);
                            if (!sentence.isEmpty()) {
                                // append white space between words
                                sb.append(" ").append(sentence);
                            }
                            dp.get(i).add(sb.toString());
                        }
                    }
                }
            }
            return dp.get(0);
        }
    
        // solution from word break I
        private boolean wordBreakOk(String s, Set<String> wordDict) {
            int len = s.length();
            // whether s[i : end] can be successfully broken
            boolean[] dp = new boolean[len + 1];
            dp[len] = true;
            for (int i = len - 1; i >= 0; i--) {
                for (int j = i; j <= len; j++) {
                    if (wordDict.contains(s.substring(i, j)) && dp[j]) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[0];
        }
    
    }
    

Log in to reply
 

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