题解 | #牛群定位系统# DFS

知识点

DFS

思路

这样例都有错误，无语==，说是按照出现的顺序排列，结果样例2根本不是

用一个最暴力的办法，把所有的字符串存在哈希表里面，把每一个位置作为第一个出现的字符开始暴力搜索可以出现的所有字符串，由于最长字符串限制在12，所以当长度达到12的时候停止搜索。

我们考虑一下时间复杂度：

除了第一个字符以外，后面还要搜索最多11个字符，由于搜索不能回头，每一步最多三个方向，计算次数为次

枚举起始点，一共144个位置，因此总体计算次数小于

考虑每个字符串哈希所有的时间为

因此计算度少于

时间限制为5秒 可以跑完

AC Code (C++)

#include <functional>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 
     * @param words string字符串vector 
     * @return string字符串vector
     */
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, -1, 0, 1};
    vector<string> findWords(vector<vector<char> >& board, vector<string>& words) {
        int n = board.size(), m = board[0].size();
        unordered_map<string, int> mp;
        for (auto& s : words) {
            mp[s] = 0;
        }

        function<void(string&, int, int)> dfs = [&](string& s, int x, int y) {
            if (s.size() > 12) return;
            s += board[x][y];
            if (mp.count(s)) {
                mp[s] = 1;
            }
            for (int i = 0; i < 4; i ++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx >= 0 and ny >= 0 and nx < n and ny < m and isalpha(board[nx][ny])) {
                    dfs(s, nx, ny);
                }
            }
            s.pop_back();
        };
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                string s;
                dfs(s, i, j);
            }
        }
        vector<string> res;
        for (auto& s : words) {
            if (mp[s]) res.push_back(s);
        }
        return res;
    }
};