广BFS(一层一层走): http://blog.csdn.net/raphealguo/article/details/7523411   节点是某种状态，边是节点与节点间的某种规则。适合: 给定初始状态跟目标状态，要求从初始状态到目标状态的最短路径。节点的子节点数量不多，树的层次不深。在树的层次较深&子节点数较多的情况下，消耗内存十分严重。

/** BFS，来自http://blog.csdn.net/raphealguo/article/details/7523411
 * @param Vs 起点
 * @param Vd 终点
 */
bool BFS(Node& Vs, Node& Vd)
{
    queue<Node> Q;   Node Vn, Vw;   int i;
    Q.push(Vs);  hash(Vs) = True; //初始状态将起点放进队列Q，设置这个节点已经访问过了, 因为已入队的节点一定会被pop会被访问

    while (!Q.empty()) //队列不空就继续搜索
    {
        Vn = Q.front();  Q.pop();  //取队列的头Vn，从队列中移除
        while(Vw = Vn通过某规则能够到达的节点)
        {
            if (Vw == Vd) {//找到终点了! 记录路径 return true;}
            if ( isValid(Vw) && !visit(Vw) ) { Q.push(Vw);  hash(Vw) = True; //Vw是一个合法节点且没有访问过，设置这个节点已经访问过了, 因为已入队的节点一定会被pop会被访问 }
        } 
    }

    return false; //无解
}

深DFS(一条路一直走到底): http://blog.csdn.net/raphealguo/article/details/7560918  适合: 给定初始状态跟目标状态，要求判断从初始状态到目标状态是否有解。难以寻找最优解(最短路)，快速寻找有解，内存消耗小。

 /**  DFS，来自http://blog.csdn.net/raphealguo/article/details/7560918
 * 前提是visit数组全部设置成false
 * @param n 当前开始搜索的节点
 * @param d 当前到达的深度，即路径长度
 * @return 是否有解
 */
bool DFS(Node n, int d)
{
    if (isEnd(n, d)) return true; //若搜索深度达到某结束状态，就返回true

    for (Node nextNode in n)  //遍历n相邻的节点nextNode
        if (!visit(nextNode))
        {
            visit[nextNode] = true; //在下一步搜索中，nextNode不能再次出现
            if (DFS(nextNode, d+1))  { //如果搜索出有解，做些其他事比如记录结果深度，return true; }
            visit[nextNode] = false; //重新设置成false，因为它有可能出现在下一次搜索的别的路径中
        } 

    return false; //本次搜索无解 
}

public class Solution {
  ​ArrayList<ArrayList<String>> all = new ArrayList<ArrayList<String>>();

  boolean isPalin(String s, int i, int j) {
    while (i<j) { // 不必i <= j
      if (s.charAt(i) != s.charAt(j)) return false;
      i++;
      j--;
    }
    return true;
  }

  void dfs(String s, int start, ArrayList<String> al) {
    if (start == s.length()) { all.add(new ArrayList<String>(al)); return; } //若搜索深度达到某结束状态，就返回
    for (int i = start + 1; i <= s.length(); i++)
      if ( isPalin(s, start, i-1) ) { //如果s的某个子串是回文串, 这里依次试遍了以start开头的每个子串
        al.add( s.substring(start, i) );  //记录本子串
        dfs(s, i, al);  //搜索剩余部分，即 s - 本子串
        al.remove( al.size()-1 );  // 本子串搜索完毕，删掉
      }    
  }

  public ArrayList<ArrayList<String>> partition(String s) {
    all.clear();
    ArrayList<String> al = new ArrayList<String>();
    dfs(s, 0, al);
    return all;
  }
}    

Variable names are all lowercase, with underscores between words. Class member variables have trailing underscores. For instance: my_exciting_local_variable, my_exciting_member_variable_.

Regular functions have mixed case; accessors and mutators match the name of the variable: MyExcitingFunction(), MyExcitingMethod(), my_exciting_member_variable(), set_my_exciting_member_variable().

class Solution 
{
  vector< vector<string> > all; //不需要new
  
  bool IsPalin(const string &s, int i, int j)
  {
    for (; i < j; i++, j--)
      if (s[i] != s[j]) return false;
    return true;  
  }

  void DFS(string s, int start, vector<string> &al)
  {
    if (start == s.length())
    {   
      all.push_back(al);
      return;
    }   
    for (int i = start + 1; i <= s.length(); i++)
      if ( IsPalin(s, start, i-1) )
      { //如果s的某个子串是回文串, 这里依次试遍了以start开头的每个子串
        al.push_back( s.substr(start, i - start) );  //记录本子串
        DFS(s, i, al);  //搜索剩余部分，即 s - 本子串
        al.pop_back();  // 本子串搜索完毕，删掉
      }   
  }

public:
  vector< vector<string> > partition(string s)  
  {
    all.clear();
    vector<string> al; //不需要new
    DFS(s, 0, al);
    return all;
  }
};

有个地方浪费了一些时间：Java的substring()和C++的substr不一样!

C++: string substr (size_t pos = 0, size_t len = npos) const;   第二个参数是长度

Java: public String substring(int beginIndex, int endIndex) 第二个参数是终止位置