两类DFS：
典型dfs_1 原型：
dfs(vector/List<?> res,vector<?> current, int i, ...) ，一般而言，i和vector<?> current共同表示当前状态
主要区别第二类在于，本类需要 在状态叶节点保存搜索到的结果
典型dfs_2 原型：
bool/int dfs(vector<?>current,int i,...) 一般而言，i和vector<?> current共同表示当前状态
主要区别第一类在于，第二类不需要保存搜索到的结果，不过一般带返回值
这两类分别在什么时候用呢？
第一类适合操作数据容器，第二类适合返回值，
Flatten Binary Tree to Linked List 两类结合
使用第一类：在p-》right链尾append新节点；
使用第二类：返回append后的链尾。
class Solution {
public:
void flatten(TreeNode *root) {
dfs(root, NULL);
}
TreeNode *dfs(TreeNode *root, TreeNode *p){
if(!root) {if(p) p->right= NULL; return p;}
TreeNode *t=root, *lc=t->left, *rc=t->right;
t->left = NULL;
if(p) p->right = t;
t = dfs(lc, t);
t = dfs(rc, t);
return t;
}
};
Restore IP Addresses 第一类
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"].
(Order does not matter)
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> res;
vector<int> lens;
dfs(res,lens,0,s);
return res;
}
inline bool isValid(char a,char b,char c){
return (a=='1'||(a=='2'&&(b<'5'||b=='5'&& c<'6')));
}
void dfs(vector<string> &res,vector<int> &lens,const int i, const string &s){//@declare i as const so it will not be changed un-consiously
if(lens.size()==4){
if(i==s.length()){
string tmp=s.substr(0,lens[0]);
int l=lens[0];
for(int i=1;i<4;i++){
tmp+="."+s.substr(l,lens[i]);////@@@error:tmp has add extra '.', so s.substr(tmp.length(),lens[i]) make s ArrayOverflow !!
l+=lens[i];
}
res.push_back(tmp);
}
return;
}
///@@warning : you should think of things more in up-to-down ways: think of every big and general conditions fully, before you do it.
//if(s[i]=='0') return ;//.0xx. is not valid in ip @@@@error: in fact '0' is valid , while '0xx' is invalid
for(int len=1;len<=3&&i+len<=s.length();len++){
if(len==2&&s[i]=='0') continue;
if(len==3&&!isValid(s[i],s[i+1],s[i+2])) continue;
lens.push_back(len);
dfs(res,lens,i+len,s);
lens.pop_back();
}
}
};
或者
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<vector<int> > res;
vector<int> cur;
dfs(res, cur, s,0);
vector<string> ss;
for(int i = 0; i< res.size(); i++){
int l = 0, k;
string tmp = "";
for(int j = 0; j<4; j++){
k = res[i][j];
tmp+=s.substr(l, k);
if(j<3) tmp+=".";
l+=k;
}
ss.push_back(tmp);
}
return ss;
}
bool isValid(const string &s, int a, int b){
if(s[a]=='0' && b>a) return false;/////////@error: 23333333333333333333333
if(b-a==2){
int n = 100*(s[a]-'0') + 10*(s[a+1]-'0') + (s[a+2]-'0');///@error: 2333333333333333
return n<=255;
}
return b-a<2;
}
void dfs(vector<vector<int> >&res, vector<int>&cur, const string &s, int idx){
if(cur.size()==4) {
if(idx==s.length()) res.push_back(cur);
return;
}
for(int i = idx; i<idx+3 && i<s.length(); i++){
if(isValid(s, idx, i)){
cur.push_back(i-idx+1);
dfs(res, cur, s, i+1);
cur.pop_back();
}
}
}
};
Word Search 第二类DFS：
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[ ["ABCE"], ["SFCS"], ["ADEE"] ]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
其中dfs()的第一个判断 ：if(b[x][y]!=w[depth])如果拿出来，速度会提高20%。
bool dfs(vector<?>current,int i,...), 其中 i：x,y current: visit.
class Solution {
public:
bool exist(vector<vector<char> > &board, string word) {
int n=board.size();
if(n==0) return word=="";
int m=board[0].size();
if(m==0) return word=="";
vector<vector<bool> > visit(n,vector<bool>(m,false));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(dfs(board,visit,0,i,j,n,m,word)) return true;
}
}
return false;
}
const int dr[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
inline bool valid(int a,int b,const int n,const int m){
return a>=0&&a<n&&b>=0&&b<m;
}
bool dfs(const vector<vector<char> > &b,vector<vector<bool> > & v,const int depth,
int x,int y,const int n,const int m,const string &w){//@@@error vector<?>v, forget &, this will cause deep_copy and timeout!
if(b[x][y]!=w[depth]) return false;//@@@error: w[depth] mistake as w[n]. Array_Index_Variable_Fault, and cause time out !!!!
if(depth==w.length()-1) return true;
v[x][y]=true;
for(int i=0;i<4;i++){
int x1=x+dr[i][0],y1=y+dr[i][1];
if(valid(x1,y1,n,m)&&!v[x1][y1]&&dfs(b,v,depth+1,x1,y1,n,m,w)){
v[x][y]=false;
return true;
}
}
v[x][y]=false;
return false;
}
};
Subsets II
Given a collection of integers that might contain duplicates, S,
return all possible subsets.
Note:
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
For example,
If S = [1,2,2],
a solution is:
[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
class Solution {
public:
typedef pair<int,int> Pr; //@@@@error: remember typedef is in function scope
vector<vector<int> > subsetsWithDup(vector<int> &S) {
sort(S.begin(),S.end());
int lst=-1,cnt=0;
vector<Pr> table;
for(int i=0;i<=S.size();i++){
if(i==S.size()||S[i]!=lst){
if(cnt>0) table.push_back(Pr(lst,cnt));
if(i<S.size()) lst=S[i],cnt=1;
else break;
}
else cnt++;
}
vector<vector<int> > res;vector<int> cur;
dfs(res,cur,0,table);
return res;
}
void dfs(vector<vector<int> > &res,vector<int> &cur,const int idx, const vector<Pr> &table){///warning: i should not be used in function paras in case of name collision with function's local vars
if(idx==table.size()) {
res.push_back(cur);
return;
}
const Pr &p=table[idx];
dfs(res,cur,idx+1,table);//no p.first
for(int i=1;i<=p.second;i++){
cur.push_back(p.first);
dfs(res,cur,idx+1,table);//@@@error: here var i collides with loop var i ! while you don't realize this i is now the loop var, not the outer i!
}
for(int i=1;i<=p.second;i++)
cur.pop_back();
}
};
带重复的全排列 第一类dfs
#include <iostream>
#include <string.h>
#include <map>
#include <set>
#include <vector>
using namespace std;
void dfs(vector<vector<int> > &res, vector<int> &cur, vector<bool> &visit, const vector<int> &num, int d){
if(d == num.size()) {
res.push_back(cur);
return;
}
for(int i=0; i<num.size(); i++){
if(!visit[i]){
if(i>0 && !visit[i-1] && num[i] == num[i-1]) continue; //@error
visit[i] = true, cur.push_back(num[i]);
dfs(res, cur, visit, num, d+1);
visit[i] = false, cur.pop_back();
}
}
}
int main(){
int a[10] = { 1, 2, 2, 4, 4, 7, 7, 7};
vector<int> num (a, a+8);
vector<bool> visit(8, false);
vector<vector<int> > res; vector<int> cur;
dfs(res, cur, visit, num, 0);
for(int i=0; i<res.size(); i++){
for(int j=0; j<res[i].size(); j++){
cout<<res[i][j]<<" ";
}cout<<endl;
}
return 0;
}