LeetCode 140: Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].

public class Solution {
    private List<String> result;
    private List<String> word;
    private Map<Integer, List<Integer>> map;
    
    public List<String> wordBreak(String s, Set<String> dict) {
        // This question is very interesting: I adopt two algorithms (Backtracking and DP) here.
        
        // Backtracking prblem
        result = new LinkedList<>();
        int n = s.length();
        
        if (n == 0)
            return result;
            
        map = new HashMap<>();
            
        if (!wordBreakCheck(s, dict))
            return result;
            
        word = new LinkedList<>();
        
        backTracking(s, n);
        
        return result;
    }
    
    private void backTracking(String s, int cnt)
    {
        if (cnt == 0)
        {
            String str = "";
            
            for (int i = word.size()-1; i >= 0; i--)
            {
                str += word.get(i);
                str += " ";
            }
            
            str = str.trim();
            result.add(str);
        }
        else
        {
            for (int i : map.get(cnt))
            {
                word.add(s.substring(i,cnt));
                backTracking(s,i);
                word.remove(word.size()-1);
            }
        }
    }
    
    // Almost same to "Word Break" question
    // We add HashMap to to record the traversal routine.
    // e.g., 7-element array (index): 0,1,2,3,4,5,6,7
    // HashMap: 7->(4,6); 6->(3); 5->(2); 4->(3,2); 3->(0); 2->(0).
    public boolean wordBreakCheck(String s, Set<String> dict) {
        // DP problem
        // If t[i] is true, it represents that the substring (from 0 to i-1) of 's' can be segmented by 'dict'. 
        boolean[] t = new boolean[s.length()+1];
        
        // Initial state: t[0] = true
        t[0] = true;
 
        for (int i = 0; i < s.length(); i++)
        {
            // Start form the next match position
            if (!t[i])
                continue;
 
            for (String a : dict)
            {
                int len = a.length();
                int end = i + len;
                
                // Overflow, match is not possible
                if (end > s.length())
                    continue;

                // If matched, mark the 'end' position.
                // Mark all of the matched 'end' positions.
                if (s.substring(i, end).equals(a))
                {
                    t[end] = true;
                    
                    if (!map.containsKey(end))
                    {
                        List<Integer> id = new LinkedList<>();
                        id.add(i);
                        map.put(end, id);
                    }
                    else
                        map.get(end).add(i);
                }
            }
        }
 
        return t[s.length()];
    } 
}