@@ -0,0 +1,1726 @@
+/*%0A * Key point: good practice for dp, first try to use recursive solution%0A *    but time limit exceed%0A */%0A%0Apublic class Solution %7B%0A    public boolean wordBreak(String s, Set%3CString%3E dict) %7B%0A        if(s == null %7C%7C s.length() == 0 %7C%7C dict == null)%0A            return true;%0A            %0A        int length = s.length();%0A%0A        //dp%5Bi%5D is true when the substring from i to the end can be partitioned%0A        boolean%5B%5D dp = new boolean%5Blength+1%5D;%0A        for(boolean b : dp)%0A            b = false;%0A            %0A        //empty string can be partitioned for sure    %0A        dp%5Blength%5D = true;    %0A        %0A        //bottom up dp, start from the end%0A        for(int i = length - 1;i%3E=0;i--)%7B%0A            for(int j = i;j %3C length;j++)%7B%0A                String sub = s.substring(i,j+1);%0A                if(dict.contains(sub) == true && dp%5Bj+1%5D == true)%7B%0A                    dp%5Bi%5D= true;%0A                    break;  //break, just jump out current level of loop%0A                %7D%0A            %7D%0A        %7D%0A        %0A        return dp%5B0%5D;%0A    %7D%0A%7D%0A%0A%0A/*********recursive solution***********/%0Apublic class Solution %7B%0A    public boolean wordBreak(String s, Set%3CString%3E dict) %7B%0A        if(dict.contains(s) == true) %0A            return true;%0A            %0A        int length = s.length();%0A        for(int i = 1;i %3C length;i++)%7B%0A            %0A            String firstPart = s.substring(0,i);%0A            if(dict.contains(firstPart) == true)%7B%0A                %0A                String remainPart = s.substring(i,length);%0A                %0A                boolean result = wordBreak(remainPart, dict);%0A                if(result == true)%7B%0A                    return true;%0A                %7D%0A            %7D%0A        %7D%0A        %0A        return false;%0A    %7D%0A%7D

Work Break, dp and recursive solution