140. Word Break II

class Solution {
    List<String> res = new ArrayList<>();
    Set<String> wordSet;
    public List<String> wordBreak(String s, List<String> wordDict) {
        int[] count = new int[26];
        for (String word : wordDict) {
            for (char c : word.toCharArray()) {
                count[c - 'a']++;
            }
        }
        
        for (char c : s.toCharArray()) {
            if (count[c - 'a'] == 0) return res;
        }
        
        wordSet = new HashSet(wordDict);
        dfs(s, 0, new StringBuilder());
        return res;
    }
    
    private void dfs(String s, int index, StringBuilder cur) {
        int n = s.length();
        if (index == n) {
            res.add(cur.toString());
            return;
        }
        
        for (int i = index; i < n; i++) {
            if (wordSet.contains(s.substring(index, i + 1))) {
                int beforeAdding = cur.length();
                if (beforeAdding == 0) {
                    cur.append(s.substring(index, i + 1));
                } else {
                    cur.append(" ");
                    cur.append(s.substring(index, i + 1));
                }
                dfs(s, i + 1, cur);
                cur.delete(beforeAdding, cur.length());
            }
        }
    }
}