public boolean wordBreak(String s, Set<String> wordDict) {
        if (s==null || s.isEmpty())
            return false;
        if (wordDict == null || wordDict.size()==0)
            return false;
        for (int i=0; i<s.length(); ++i) {
            if (wordDict.contains(s.substring(0, i+1)) && wordBreak(s.substring(i+1), wordDict))
                return true;
        }
        return false;
    }