A Java solution with similar DP idea


  • 10
    R

    The idea is pretty similar to other DP solution.
    1)keep all positions which could form substring contained in the set in a linkedlist

    1. Iterate the target string, check substring between current position and stored positions. If new sub string hits the dictionary,add it the front of linkedlist
      3)After iteration, check if the front element of linkedlist equals to the length of string.

    It consumes 296ms

    This solution is still a time O(n^2) and space O(n) one. It is better if dictionary contains long words.

    public class Solution {
        public boolean wordBreak(String s, Set<String> dict) {
            if (s==null||s.length()==0) return false;
            else if (dict.contains(s)) return true;
            
            List<Integer> starts = new LinkedList<Integer>();
            starts.add(0);
           
            for (int end=1;end<=s.length();end++){
            	boolean found=false;
                for (Integer start:starts)
                    if (dict.contains(s.substring(start,end))){
                    	found=true;
                    	break;
                    }
                if(found)  starts.add(0,end);
            }
    
            return (starts.get(0)==s.length());
        }
    }

  • 0
    R

    I am little bit curious since almost all my posts have been edited by Shangrila. I can't help asking what part is edited(removed or added).


  • 0
    S

    I corrected your code format. Since you alway left the last } out of code box. FYI, formatting code is to select all code then press {} button.


  • 0
    G

    I'd bold the "start" variable in the code as well. It took me a while to see that it's used in the substring (given that only "end" is bolded).


  • 2
    R

    I feel like this version is more concise.

    public class Solution {
        public boolean wordBreak(String s, Set<String> dict) {
            if (s==null||s.length()==0) return false;
            else if (dict.contains(s)) return true;
            
            List<Integer> starts = new LinkedList<Integer>();
            starts.add(0);
           
            for (int end=1;end<=s.length();end++)
                for (int i=0;i<starts.size();i++)
                    if (dict.contains(s.substring(starts.get(i),end))){
                    	starts.add(0,end);
                    	break;
                    }
            return (starts.get(0)==s.length());
        }
    }

  • 0
    R

    Another Python version

    class Solution:
    # @param s, a string
    # @param dict, a set of string
    # @return a boolean
    def wordBreak(self, s, dict):
        if s is None or dict is None:
            return False
        if s in dict:
            return True
        starts=[0]
        for i in range(1,len(s)+1):
            for j in range(0,len(starts)):
                if s[starts[j]:i] in dict:
                    starts.insert(0,i)
                    break
        
        return starts[0]==len(s)

  • 0
    D

    why is it O(n^2)?

    I think the following:
    outer loop happens at most n times,
    inner loop happens at most n times and
    inside the inner you are calling substring which is order of size of substring since java 7

    so the complexity would be O(n^3). Correct me please if I am wrong


  • 0
    B

    the substring() call the System native arraycopy() method, seems O(1) time, not O(n) time.


Log in to reply
 

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