Accepted Java Solution


  • 33
    A
    public class Solution {
        public boolean wordBreak(String s, Set<String> dict) {
            boolean [] breakable = new boolean[s.length()+1];
            breakable[0] = true;
    
            for(int i=1;i<=s.length();i++){
                for(int j=0;j<i;j++){
                    if(breakable[j]&&dict.contains(s.substring(j,i))){
                        breakable[i] = true;
                        break;
                    }
                }
            }
            return breakable[s.length()];
        }
    }

  • 7
    V

    Can you please explain the solution ?


  • 6
    A

    It is a DP solution, the array breakable[i] stores whether the substring s.substring(0,i) is breakable or not. The DP equation is as follows:
    breakable[i+1] |= breakable[j]&&dict.contains(s.substring(j,i+1)), j>=0 && j<i+1


  • 0
    B

    what is the runtime? O(n^3)?


  • 0
    A

    looks like n^2 worst case


  • 0
    W

    if s is "abcabcabc" and the set is ["abc"]
    the result will be true but it should be false.
    Am I wrong?


  • 1
    E

    @www2277843987, no, it should be true. The problem didn't state that words in dictionary cannot be reused.


  • 4
    M

    s.substring() is O(n) operation. So I guess it's O(n^3) worst case.


  • 0
    X
    This post is deleted!

  • 0
    S

    @www2277843987 the result will be false as it returns breakable[s.length()] and in your case breakable[10] will be false and only breakable[4] is true. and the runtime is N^2


  • 0
    G

    it is pretty clear and clean, thanks for sharing @acmachine

    I have a question though. When I saw your code, I thought using a HashSet would be even faster, since you always call list.contains, it would save a lot of time. But when I submitted I noticed that my solution with the hashset is even more slow then the regular one. Do you guys&gals have any idea what might have gone wrong? Here is my code:

    class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            HashSet<String> dictionary =  new HashSet<String>(wordDict);
            boolean[] found = new boolean[s.length()+1];
            found[0] = true;
            for(int i = 0; i<s.length()+1; i++){
                for(int j = 0; j<s.length(); j++){
                    if(found[j]&& dictionary.contains(s.substring(j,i)) ){
                        found[i] = true;
                        break;
                    }
                }
            }
            return found[s.length()];
        }
    }
    

    Thanks.


Log in to reply
 

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