http://leetcode.com/onlinejudge#question_131
这道题看了别人的深度优先搜索,基本上套用过来,过了。
深度优先搜索可以是一个递归,不同于普通的递归是:普通的递归一般为:
void func() {
//terminated condition
//do sth..
func();
}
而深度优先搜索的形式一般为:
void func() {
//terminated condition 中止条件肯定是有的
//do sth..
for ( ... ) { //当前层所有的可能往下一层走的分支,但是因为for是一次一次执行循环的,所以func会不停地往下调用,直到调用到terminated condition为止,然后再回退,回退到当前层的for的下一次循环
func(); //注意这里,在当前层,func会递归执行很多次
}
}
思考深度优先搜索的时候,不需要从全局的思路去考虑,而是只要考虑当前层,往下递归,往上回退,以及for循环,这几个逻辑即可。
好了,上代码,鼓捣了一晚上没鼓捣对,第二天又改了改,改对了。
import java.util.ArrayList; public class Solution { public ArrayList<ArrayList<String>> all = new ArrayList<ArrayList<String>>(); public ArrayList<String> al = new ArrayList<String>(); public String str; public ArrayList<ArrayList<String>> partition(String s) { // Start typing your Java solution below // DO NOT write main() function all.clear(); al.clear(); str = s; dfs(0); return all; } private void dfs(int index) { if (index == str.length()) { ArrayList<String> alNew = new ArrayList<String>(al); all.add(alNew); } for (int i = index; i < str.length(); i++) { String curr = str.substring(index, i+1); if (isPalin(curr)) { al.add(curr); dfs(i+1); al.remove(al.size()-1); } } } private boolean isPalin(String s) { int i = 0; int j = s.length()-1; while(i<j) { if (s.charAt(i) != s.charAt(j)) return false; i++; j--; } return true; } public static void main(String[] args) { String s = "aaddasb"; Solution sl = new Solution(); sl.partition(s); for (int i = 0; i < sl.all.size(); i++) { ArrayList<String> internal = sl.all.get(i); for (int j = 0; j < internal.size(); j++) { System.out.print(internal.get(j) + " "); } System.out.println(); } } }
看官请去掉main来提交代码。
接下来会看看这道题目有DP算法没,之前在网上看到过。
同时还得锻炼锻炼自己的DFS思维,之后做做http://leetcode.com/onlinejudge#question_93 关于IP地址的所有可能组合这道题目,加深DFS理解。