Java DFS + Memorization Solution, beats 92%


  • 0
    S
    public boolean wordBreak(String s, Set<String> wordDict) {
            if (s == null || s.length() == 0) {
                return false;
            }
            int maxLength = maxLengthStr(wordDict);
            return dfs(s, 0, wordDict, new boolean[s.length()], maxLength);
        }
        
        private boolean dfs(String s, int idx, Set<String> wordDict, boolean[] unbreakable, int maxLength) {
            if (idx >= s.length()) {
                return true;
            } else if (unbreakable[idx]) {
                return false;
            } else {
                int end = Math.min(idx + maxLength, s.length());
                for (int i = idx + 1; i <= end; i++) {
                    if (wordDict.contains(s.substring(idx, i))) {
                        if (dfs(s, i, wordDict, unbreakable, maxLength)) {
                            return true;
                        }
                    }
                }
                unbreakable[idx] = true;
                return false;
            } 
        }
        
        private int maxLengthStr(Set<String> wordDict) {
            int max = 0;
            for (String str : wordDict) {
                max = Math.max(max, str.length());
            }
            return max;
        }

Log in to reply
 

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