Java DFS and DP comparision


  • 0

    node: a valid position

    edge: 2 valid position which linked by a word in dict.
    Both are O(n^2) time and O(n) space

       public class Solution {
            public boolean wordBreak(String s, Set<String> wordDict) {
                if (s == null || s.isEmpty()) {
                    return false;
                }
                boolean[] visited = new boolean[s.length() + 1];
                return wordBreakHelper(s, visited, 0, wordDict);
            }
            
            private boolean wordBreakHelper(String s, boolean[] visited, int pos, Set<String> wordDict) {
                if (pos == s.length()) {
                    return true;
                }
                visited[pos] = true;
                for (int i = pos + 1; i <= s.length(); i++) {
                    if (!visited[i] && wordDict.contains(s.substring(pos, i)) && wordBreakHelper(s, visited, i, wordDict)) {
                        return true;
                    }
                }
                return false;
            }
        }
    
    
    public class Solution {
        public boolean wordBreak(String s, Set<String> wordDict) {
            if (s == null || s.isEmpty()) {
                return false;
            }
            
            int n = s.length();
            boolean[] breakable = new boolean[n + 1];
            breakable[0] = true;
            for (int i = 1; i <= n; i++) {
                for (int j = i - 1; j >= 0; j--) {
                    if (breakable[j] && wordDict.contains(s.substring(j, i))) {
                        breakable[i] = true;
                        break;
                    }
                }
            }
            return breakable[n];
        }
    }

Log in to reply
 

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