@@ -0,0 +1,1407 @@
+/***%0A * Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.%0A *%0A * For example, given%0A * s = %22leetcode%22,%0A * dict = %5B%22leet%22, %22code%22%5D.%0A *%0A * Return true because %22leetcode%22 can be segmented as %22leet code%22.%0A */%0Apublic class Solution %7B%0A    // Solution 1: DFS O(2%5En) O(n)%0A    //%0A    public boolean wordBreak(String s, Set%3CString%3E dict) %7B%0A        return dfs(s, dict, 0, 0);%0A    %7D%0A%0A    private boolean dfs(String s, Set%3CString%3E dict, int start, int cur) %7B%0A        if (cur == s.length()) %7B%0A            return dict.contains(s.substring(start, s.length()));%0A        %7D%0A%0A        if (dfs(s, dict, start, cur + 1)) return true;%0A        if (dict.contains(s.substring(start, cur + 1)))%0A            if (dfs(s, dict, cur + 1, cur + 1))  return true;%0A        return false;%0A    %7D%0A%0A    // Solution 2: DP O(n%5E2) O(n)%0A    // f%5Bi%5D = f%5Bj1%5D && check(i, j1) %7C%7C f%5Bj2%5D && check(i, j2) %7C%7C ...%0A    // (0 %3C= j %3C i)%0A    public boolean wordBreak(String s, Set%3CString%3E dict) %7B%0A        int n = s.length();%0A        boolean f%5B%5D = new boolean %5Bn + 1%5D;%0A        f%5B0%5D = true;%0A        for (int i = 1; i %3C= n; i++) %7B%0A            for (int j = i - 1; j %3E= 0; j--) %7B%0A                if (f%5Bj%5D && dict.contains(s.substring(j, i))) %7B%0A                    f%5Bi%5D = true;%0A                    break;%0A                %7D%0A            %7D%0A        %7D%0A        return f%5Bn%5D;%0A    %7D%0A%7D%0A

add WordBreak.java