@@ -0,0 +1,2167 @@
+/***%0A * 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.%0A *%0A * Return all such possible sentences.%0A *%0A * For example, given%0A * s = %22catsanddog%22,%0A * dict = %5B%22cat%22, %22cats%22, %22and%22, %22sand%22, %22dog%22%5D.%0A *%0A * A solution is %5B%22cats and dog%22, %22cat sand dog%22%5D.%0A */%0Aimport java.util.List;%0Aimport java.util.ArrayList;%0Aimport java.util.Set;%0Aimport java.util.HashSet;%0Apublic class WordBreakII %7B%0A    // Solution DP + DFS O(n%5E2) O(n%5E2)%0A    public List%3CString%3E wordBreak(String s, Set%3CString%3E dict) %7B%0A        int n = s.length();%0A        boolean f%5B%5D = new boolean %5Bn + 1%5D;%0A        boolean prev%5B%5D%5B%5D = new boolean%5Bn + 1%5D%5Bn%5D;%0A        f%5B0%5D = true;%0A        for (int i = 1; i %3C= n; i++)%0A            for (int j = i - 1; j %3E= 0; j--)%0A                if (f%5Bj%5D && dict.contains(s.substring(j, i)))%7B%0A                    f%5Bi%5D = true;%0A                    prev%5Bi%5D%5Bj%5D = true;%0A                %7D%0A        for (boolean b: f)%0A            System.out.printf(%22%25b%5Cn%22, b);%0A        List%3CString%3E ret = new ArrayList%3CString%3E();%0A        List%3CString%3E path = new ArrayList%3CString%3E();%0A        genPath(s, ret, prev, path, n);%0A        return ret;%0A    %7D%0A%0A    private void genPath(String s, List%3CString%3E ret, boolean%5B%5D%5B%5D prev, List%3CString%3E path, int cur) %7B%0A        if (cur == 0) %7B%0A            StringBuffer sb = new StringBuffer();%0A            for (int i = path.size() - 1; i %3E= 0; i--)%0A                sb.append(path.get(i) + %22 %22);%0A            sb.setLength(sb.length() - 1);%0A            ret.add(sb.toString());%0A            return;%0A        %7D%0A        for (int i = 0; i %3C s.length(); i++) %7B%0A            if (prev%5Bcur%5D%5Bi%5D) %7B%0A                path.add(s.substring(i, cur));%0A                genPath(s, ret, prev, path, i);%0A                path.remove(path.size() - 1);%0A            %7D%0A        %7D%0A    %7D%0A%0A    public static void main(String args%5B%5D) %7B%0A        WordBreakII wb2 = new WordBreakII();%0A        Set%3CString%3E dict = new HashSet%3CString%3E();%0A        dict.add(%22a%22);%0A        dict.add(%22b%22);%0A        dict.add(%22c%22);%0A        List%3CString%3E result = wb2.wordBreak(%22abc%22, dict);%0A        for (String s: result)%0A            System.out.printf(%22%25s%5Cn%22, s);%0A    %7D%0A%7D%0A

add WordBreakII.java