| 7 | return recur(s,dictionarySet,0); |
| 8 | } |
| 9 | public int recur(String s, HashSet<String> dictionary, int index){ |
| 10 | if(index==s.length()){ //empty string |
| 11 | return 0; |
| 12 | } |
| 13 | if(dp[index]!=-1){ |
| 14 | return dp[index]; |
| 15 | } |
| 16 | StringBuilder sb = new StringBuilder(); |
| 17 | int minExtraChar = Integer.MAX_VALUE; |
| 18 | for(int i=index;i<s.length();i++){ |
| 19 | sb.append(s.charAt(i)); //l |
| 20 | int extraChar = 0; |
| 21 | if(!dictionary.contains(sb.toString())){ |
| 22 | extraChar = sb.length(); |
| 23 | } |
| 24 | int curExtra = recur(s,dictionary,i+1); |
| 25 | minExtraChar = Math.min(minExtraChar,extraChar + curExtra); |
| 26 | } |
| 27 | return dp[index] = minExtraChar; |
| 28 | } |
| 29 | } |