[java/2ms] Backward BFS.


  • 0

    Shorten @Nakanu code :)
    The thinking is similar to BFS, in which way it looks forward maxLen steps. However, the major difference here is that it looks backward maxLen steps at most and can terminate in advance.

    public boolean wordBreak(String s, Set<String> wordDict) {
            boolean[] dp = new boolean[s.length()+1];
            dp[0] = true;
            int maxLen = 0;
            for (String str : wordDict) maxLen = Math.max(maxLen, str.length());
            
            for(int end = 1; end < s.length()+1; end++) {
    // looks back
                for(int j = end-maxLen > 0? end-maxLen : 0;j < end; 
                    if(dp[i] && wordDict.contains(s.substring(i,end))){
                        dp[end] = true;
                        break;
                    }
                }
            }
            return dp[s.length()];
        }
    

    my recursive version, DFS, 4ms

    // recursive
        public boolean wordBreak(String s, Set<String> wordDict) {
            if (s == null || wordDict == null)
                return false;
            boolean[] visited = new boolean[s.length() + 1];
            return search(s, wordDict, 0, visited);
        }
    
        private boolean search(String s, Set<String> wd, int start, boolean[] visited) {
            if (start == s.length())
                return true;
            // sub part breakable
            if (visited[start])
                return false;
            // traverse
            for (int i = start, end = start+1; i < s.length(); i++, end++) {
                // contains substring
                if (!visited[end] && wd.contains(s.substring(start, end))
                        && search(s, wd, end, visited)) {
                    return true;
                }
            }
            visited[start] = true;
            return false;
        }
    

Log in to reply
 

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