Accepted Java Solution

  • 33
    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++){
                        breakable[i] = true;
            return breakable[s.length()];

  • 7

    Can you please explain the solution ?

  • 6

    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

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

  • 0

    looks like n^2 worst case

  • 0

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

  • 1

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

  • 4

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

  • 0
    This post is deleted!

  • 0

    @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

    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;
            return found[s.length()];


Log in to reply

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