public List<String> wordBreak2(String s, Set<String> dict)//AC
    {
    	if (s == null || s.length() == 0)
    		return new ArrayList<String>();
    	
    	int len = s.length();
    	List<Integer>[] lists = new ArrayList[len];
    	for (int i = 0; i < len; ++i)
    	{
    		lists[i] = new ArrayList<Integer>();
    	}
    	
    	for (int end = 1; end <= len; ++end)
    	{
    		for (int start = 0; start < end; ++start)
    		{
    			String tmp = s.substring(start, end);
    			if (dict.contains(tmp))
    			{
    				if (start == 0 || !lists[start-1].isEmpty())
    				{
    					lists[end-1].add(start);
    				}
    			}
    		}
    	}
    	return rebuildList(lists, s, len-1);
    }