|
| 1 | +packageAlgorithms.dfs; |
| 2 | + |
| 3 | +importjava.util.ArrayList; |
| 4 | +importjava.util.HashMap; |
| 5 | +importjava.util.List; |
| 6 | + |
| 7 | +publicclassPartition { |
| 8 | +publicList<List<String>>partition(Strings) { |
| 9 | +List<List<String>>ret =newArrayList<List<String>>(); |
| 10 | +List<String>path =newArrayList<String>(); |
| 11 | + |
| 12 | +if (s ==null) { |
| 13 | +returnret; |
| 14 | + } |
| 15 | + |
| 16 | +HashMap<String,Boolean>map =newHashMap<String,Boolean>(); |
| 17 | + |
| 18 | +dfs(s,path,ret,0,map); |
| 19 | + |
| 20 | +returnret; |
| 21 | + } |
| 22 | + |
| 23 | +publicbooleanisPalindrom(Strings) { |
| 24 | +intlen =s.length(); |
| 25 | +if (len <=1) { |
| 26 | +returntrue; |
| 27 | + } |
| 28 | + |
| 29 | +intleft =0; |
| 30 | +intright =len -1; |
| 31 | +for (;left <right;left++,right--) { |
| 32 | +if (s.charAt(right) !=s.charAt(left)) { |
| 33 | +returnfalse; |
| 34 | + } |
| 35 | + } |
| 36 | + |
| 37 | +returntrue; |
| 38 | + } |
| 39 | + |
| 40 | +/* |
| 41 | + we use a map to store the solutions to reduce the times of computing. |
| 42 | + */ |
| 43 | +publicvoiddfs(Strings,List<String>path,List<List<String>>ret,intindex,HashMap<String,Boolean>map) { |
| 44 | +if (index ==s.length()) { |
| 45 | +ret.add(newArrayList<String>(path)); |
| 46 | +return; |
| 47 | + } |
| 48 | + |
| 49 | +for (inti =index;i <s.length();i++) { |
| 50 | +Stringsub =s.substring(index,i +1); |
| 51 | + |
| 52 | +Booleanflag =map.get(sub); |
| 53 | +if (flag ==null) { |
| 54 | +flag =isPalindrom(sub); |
| 55 | +map.put(sub,flag); |
| 56 | + } |
| 57 | + |
| 58 | +if (!flag) { |
| 59 | +continue; |
| 60 | + } |
| 61 | + |
| 62 | +path.add(sub); |
| 63 | +dfs(s,path,ret,i +1,map); |
| 64 | +path.remove(path.size() -1); |
| 65 | + } |
| 66 | + } |
| 67 | + |
| 68 | +/* |
| 69 | + * Solution 2: Use DP to reduce the duplicate count. |
| 70 | + * */ |
| 71 | +boolean[][]isPalindromDP(Strings) { |
| 72 | +intlen =s.length(); |
| 73 | +boolean[][]ret =newboolean[len][len]; |
| 74 | + } |
| 75 | + |
| 76 | +} |