My Java Solution based on DFS + Pruning Beats 99%


  • 1
    Y
    • Find the length of longest word in wordDict, use it to restrict the search space;
    • Use the idea in Word Break I for pruning. Check if the string is breakable firstly. If not, return early.
    public class Solution {
        public List<String> wordBreak(String s, List<String> wordDict) {
            
            List<String> result = new ArrayList<>();
            if (wordDict == null || wordDict.isEmpty()) {  // corner case 1
                return result;
            }
            if (s == null || s.isEmpty()) {  // corner case 2
                result.add("");
                return result;
            }
            
            // set.contains() is faster than list.contains()
            Set<String> dict = new HashSet<>(wordDict);
            
            // used for optimization
            int maxLengthOfWord = getMaxLength(wordDict);
            
            // 1. use DP to find which substrings are breakable, dp[i] represents if s.substring(i) is breakable
            int len = s.length();
            boolean[] dp = new boolean[len + 1];
            dp[len] = true;
            for (int i = len - 1; i >= 0; i--) {
                for (int j = 1; j <= Math.min(len - i, maxLengthOfWord); j++) {
                    dp[i] = dp[i + j] && dict.contains(s.substring(i, i + j));
                    if (dp[i]) {
                        break;
                    }
                }
            }
            
            // 2. dfs
            dfs(s, dict, dp, maxLengthOfWord, 0, "", result);
            
            return result;
        }
        
        // dfs + backtracking
        private void dfs(String s, Set<String> dict, boolean[] isBreakable, int maxLengthOfWord, int start, String sentence, List<String> result) {
            
            if (start == s.length()) {
                sentence = sentence.substring(0, sentence.length() - 1);  // remove the trailing space
                result.add(sentence);
                return;
            }
            
            // pruning: if the substring is not breakable, return early
            if (!isBreakable[start]) {
                return;
            }
            
            for (int i = 1; i <= Math.min(s.length() - start, maxLengthOfWord); i++) {
                String word = s.substring(start, start + i);
                if (dict.contains(word)) {
                    dfs(s, dict, isBreakable, maxLengthOfWord, start + i, sentence + word + " ", result);
                }
            }
        }
        
        // get the maximum length of word in dict
        private int getMaxLength(List<String> wordDict) {
            int maxLengthOfWord = 0;
            for (String word : wordDict) {
                maxLengthOfWord = Math.max(maxLengthOfWord, word.length());
            }
            return maxLengthOfWord;
        }
    }
    

Log in to reply
 

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