搜索类型bfs, dfs, dp的一点感想

blue_epoch

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

最近做了几道搜索类的题，有一些小感触如下：
主要用126 Word Ladder II 和 140 Word Break 举例。

搜索类题目大致可以用三种方法，BFS，DFS或者DP。

BFS的优势主要在于可以让我们处理同层元素，比如126题每改动一个字符需要加上1个距离，由于一个词可能可以有多种改动1个字符变成另一个词的方法，而这些新词距离都是原词距离+ 1，所以用BFS可以让我们知道现在走到多少层了。

DFS的优势主要在于打印路径。因为BFS用的是Queue，里面一般只存当前元素，或者最多加上一个距离。所以当我们需要找路径时，一般就要用到DFS了。DFS找路径分为两种，一种是打印所有可能的路径，这个时候有两种方法：
一种是返回List，这种方法有点recursion的味道。把当前值和往后所有可能的值拼起来，添加到path里面。

public List<String> allPath (Map<Integer, List<Integer>> graph, int start) {
return searchPath(graph, start);
}
public List<String> searchPath(Map<Integer, List<Integer>> graph, int start) {
List<String> path = new ArrayList<>();
if (!graph.containsKey(start) || graph.get(start).size() == 0) {
path.add(start + "");
return path;
}
List<Integer> nexts = graph.get(start);
for (int next : nexts) {
List<String> sols = searchPath(graph, next);
for (String sol : sols) {
path.add(start + " " + sol);
}
}
return path;
}

复制代码

另一种是返回void，每次走到最后时在res中添加path

public List<String> allPath2 (Map<Integer, List<Integer>> graph, int start) {
List<String> res = new ArrayList<>();
StringBuilder path = new StringBuilder();
path.append(start + " ");
searchPath2(graph, start, path, res);
return res;
}
public void searchPath2(Map<Integer, List<Integer>> graph, int start, StringBuilder path, List<String> res) {
if (!graph.containsKey(start) || graph.get(start).size() == 0) {
res.add(path.toString());
return;
}
List<Integer> nexts = graph.get(start);
for (int next : nexts) {
String s = " " + next;
path.append(s);
searchPath2(graph, next, path, res);
path.delete(path.length() - s.length(), path.length());
}
}

复制代码

如果可能出现重复搜索，比如Word Break II，某串字符可能在前后同时出现，为了避免又一次拆分搜索，可以把字符和它对应的拆分结果(list)存起来，就是memo一下。这样之后再遇到这个小伙伴就可以直接调用啦。
代码如下， map的工作就是memo，如果去掉map相关程序结果一样，但时间会慢不少。

public List<String> wordBreak(String s, List<String> wordDict) {
return DFS(s, wordDict, new HashMap<String, List<String>>());
}
List<String> DFS(String s, List<String> wordDict, Map<String, List<String>>map) {
if (map.containsKey(s))
return map.get(s);
List<String>res = new LinkedList<String>();
if (s.length() == 0) {
res.add("");
return res;
}
for (String word : wordDict) {
if (s.startsWith(word)) {
List<String>sublist = DFS(s.substring(word.length()), wordDict, map);
for (String sub : sublist)
res.add(word + (sub.isEmpty() ? "" : " ") + sub);
}
}
map.put(s, res);
return res;
}

复制代码

另一种，需要打印最短/最长路径的所有可能路径。
如果没有环比较容易, 在之前代码基础上加上记录路径长度的变量total和保存最长路径的max即可。

public List<Integer> longestPath (Map<Integer, List<Couple>> graph, int start, int total) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
path.add(start);
int[] max = new int[]{Integer.MIN_VALUE};
search(graph, start, 0, max, res, path);
return res.get(res.size() - 1);
}
public void search(Map<Integer, List<Couple>> graph, int start, int total, int[] max, List<List<Integer>> res, List<Integer> path) {
if (!graph.containsKey(start) || graph.get(start).size() == 0) {
if (max[0] < total) {
max[0] = total;
res.add(new ArrayList<>(path));
}
return;
}
List<Couple> pairs = graph.get(start);
for (Couple pair : pairs) {
int next = pair.node;
int dist = pair.dist;
path.add(next);
search(graph, next, total + dist, max, res, path);
path.remove(path.size() - 1);
}
}

复制代码

但是有环的时候比较复杂。
其实一般来说，就算要的是“最”路径，DFS也可以，但是126 Word Ladder用了BFS+DF。word break给定一串字符，往后走，走走总是可以走完的(要么匹配到最后，要么没有next)，但是word ladder可能出现字符串a变动一个字符到b,结果b变动一个字符又到了a，这种情况怎么办呢？我第一反应是DFS加个visited。DFS加visited又有两种情况，一种是遇到一个点以后就再也不愿意看见它了，这种情况肯定不能用在这里，因为不同路径可走向同一个字符串，这是允许的。另一种是同一条路径不能出现重复字符串。这种情况在dfs前后分别add,remove那个字符就行。但是这道题要求最短路径。DFS的一大缺点就是所有路径都会走完，哪怕prune一下(之前保存过某个距离且路径长度超过之前保存的距离的直接return)，但花费时间还是很大，而且存在先加了一些长距离的后面又逐步加短距离的(DFS我们无法控制它先走那条，它需要一条路径搜索到底再走另一条)，我们拿到res以后还要从后往前遍历看。所以先用BFS找最短路径长的同时保存一下neighbors，之后再用DFS通过neighbors找到所有路径更为快捷。

DP的方法可以参照unique path。一般来说，如果是单个方向走，比如只可以往下往右走，用dp更新，非常直接明了。最后return dp[长][宽]即可。

欢迎大家补充。

[二分/排序/搜索] 搜索类型bfs, dfs, dp的一点感想

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

本帖被以下淘专辑推荐:

浏览过的版块