My BFS and DFS Solution


  • 0

    BFS

    public boolean wordBreak(String s, List<String> wordDict) {
        Collections.sort(wordDict, new Comparator<String>(){
            @Override
            public int compare(String s1, String s2){
                return s1.length() - s2.length();
            }
        });
        boolean[] memo = new boolean[s.length()+1];
        Queue<Integer> toCheck = new LinkedList<>();
        toCheck.offer(0);
        while(toCheck.peek()!=null){
            int i = toCheck.poll();
            for(String word: wordDict){
                int ni = i + word.length();//excluded ni
                if(ni>s.length()) break; //Since the list is already sorted by string length.
                if(memo[ni]) continue;
                if(s.substring(i,ni).equals(word)){
                    memo[ni] = true;
                    if(ni==s.length()) return true;
                    toCheck.offer(ni);
                }
            }
        }
        return false;
    }
    

    DFS

    boolean[] memo;
    public boolean wordBreak(String s, List<String> wordDict) {
        Collections.sort(wordDict, new Comparator<String>(){
            @Override
            public int compare(String s1, String s2){
                return s1.length() - s2.length();
            }
        });
        memo = new boolean[s.length()+1];
        return dfs(s,0,wordDict);
    }
    private boolean dfs(String s, int i, List<String> wordDict){
        for(String word: wordDict){
            int ni = i + word.length();
            if(ni>s.length()) return false;
            if(memo[ni]) continue;
            if(s.substring(i,ni).equals(word)){
                memo[ni] = true;
                if(ni==s.length()) return true;
                if(dfs(s,ni,wordDict)) return true;
            }
        }
        return false;
    }

Log in to reply
 

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