@@ -0,0 +1,997 @@
+import java.util.*;%0A%0Apublic class Solution %7B%0A    public boolean wordBreak(String s, Set%3CString%3E wordDict) %7B%0A        int n = s.length();%0A        mark = new int%5Bn%5D%5Bn%5D;%0A        for(int i=0; i%3Cn; i++) for(int j=0; j%3Cn; j++) mark%5Bi%5D%5Bj%5D = -1;%0A        dfs(s, wordDict, 0, n-1);%0A        return mark%5B0%5D%5Bn-1%5D == 1;%0A    %7D%0A    %0A    private int%5B%5D%5B%5D mark;%0A    %0A    private void dfs(String s, Set%3CString%3E wordDict, int i, int j) %7B%0A        if(mark%5Bi%5D%5Bj%5D != -1) return;%0A        %0A        mark%5Bi%5D%5Bj%5D = 0;%0A        for(String a : wordDict) %7B%0A            if(a.length() %3E (j-i+1)) continue;%0A            if(s.substring(i, i + a.length()).compareTo(a) == 0) %7B%0A                mark%5Bi%5D%5Bi + a.length()-1%5D = 1;%0A                if(a.length() + i %3C= j) %7B%0A                    dfs(s, wordDict, i + a.length(), j);%0A                    if(mark%5Bi + a.length()%5D%5Bj%5D == 1) %7B%0A                        mark%5Bi%5D%5Bj%5D = 1;%0A                        return;%0A                    %7D%0A                %7D%0A                %0A            %7D%0A        %7D%0A    %7D%0A%7D%0A

Create Word_Break.java