Is my solution DP or Brute Force?


  • 0
    G

    Is my solution DP or Brute Force? What is the time complexity?

    public List<String> wordBreak2(String line, int startIndex, Set<String> words)
    {
    	return wordBreakWithCache(line, startIndex, words, new HashMap<Integer, List<String>>());
    }
    
    public List<String> wordBreakWithCache(String line, int startIndex, Set<String> words, HashMap<Integer, List<String>> cache)
    {
    	if (line.length() == startIndex)
    		return new ArrayList<String>();
    
    	if (cache.containsKey(startIndex))
    		return cache.get(startIndex);
    	else
    	{
    		List<String> breaks = new ArrayList<String>();
    		for (String word : words)
    		{
    			if (line.startsWith(word, startIndex))
    			{
    				List<String> tailBreaks = wordBreakWithCache(line, startIndex + word.length(), words, cache);
    
    				if (tailBreaks.size() > 0)
    					breaks.addAll(appendMap(word + " ", tailBreaks));
    				else if (line.length() - startIndex - word.length() == 0)
    					breaks.add(word);
    			}
    		}
    		assert cache.containsKey(startIndex) == false;
    		cache.put(startIndex, breaks);
    
    		return breaks;
    	}
    }
    
    private Collection<? extends String> appendMap(String prefix, List<String> tailBreaks)
    {
    	ArrayList<String> newList = new ArrayList<String>(tailBreaks.size());
    	for (int i = 0; i < tailBreaks.size(); i++)
    		newList.add(prefix + tailBreaks.get(i));
    
    	return newList;
    }

Log in to reply
 

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