Please compare these two solutions


  • 0
    C

    Solution I: Time Complexity nm(n is the length of s and m is the size of dict)

    public List<String> wordBreak(String s, Set<String> dict) {
        List<List<String>> result=new ArrayList<List<String>>();
        if(s.isEmpty()||dict.isEmpty()) return new ArrayList<String>(); 
        if(!isValid(s,dict)) return new ArrayList<String>(); 
        for(int i=0;i<s.length();i++)
        {
            result.add(new ArrayList<String>());
        }
        for(int i=0;i<s.length();i++)
        {
            if(i==0||!result.get(i-1).isEmpty())
            {
                for(String str:dict)
                {
                    if(i+str.length()-1<s.length()&&str.equals(s.substring(i,i+str.length())))
                    {
                        if(i==0)  result.get(i+str.length()-1).add(str);
                        else
                        {
                            for(String pre:result.get(i-1))
                            {
                                result.get(i+str.length()-1).add(pre+" "+str);
                            }
                        }
                    }
                }
            }
        }
        return result.get(result.size()-1);
    }
    

    Solution II Time Complexity n*n (n is the length of s)

    public List<String> wordBreak(String s, Set<String> dict) {
        List<List<String>> result=new ArrayList<List<String>>();
        if(s.isEmpty()||!isValid(s,dict)) return new ArrayList<String>();
        for(int i=0;i<s.length();i++)
        {
            result.add(new ArrayList<String>());
            for(int j=i;j>=0;j--)
            {
                String cur=s.substring(j,i+1);
                if((j==0||result.get(j-1).size()>0)&&dict.contains(cur))
                {
                    if(j==0) result.get(i).add(cur);
                    else{
                        for(String pre:result.get(j-1))
                        {
                            result.get(i).add(pre+" "+cur);
                        }
                    }
                }
            }
        }
        return result.get(s.length()-1);
        
    }
    

    Am I correct on the time complexities for both solutions? and which one is preferable in a interview?


Log in to reply
 

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