Simplest Backtracking Only C++ Solution (Accepted!), 1155 ms


  • 0
    M
    class Solution {
    private:
        vector<bool> used;
        vector< pair<int, int> > const c_steps = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        
    public:
        bool Check(vector<char> const & b, int N, string const & w, int pw, int pi, int pj) {
            if (pw >= w.size()) return true;
            int pos = pi * N + pj;
            if (used[pos] || b[pos] != w[pw]) return false;
            used[pos] = true;
            bool found = false;
            for (int i = 0; i < c_steps.size(); ++i) {
                if (Check(b, N, w, pw + 1, pi + c_steps[i].first, pj + c_steps[i].second)) {
                    found = true;
                    break;
                }
            }
            used[pos] = false;
            return found;
        }
        
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            if (board.empty() || words.empty()) return {};
            sort(words.begin(), words.end());
            vector<string> result;
            int m = board.size(), n = board[0].size(), M = m + 2, N = n + 2;
            used.resize(M * N);
            vector<char> b(M * N);
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    b[(i + 1) * N + (j + 1)] = board[i][j];
                }
            }
            for (int wi = 0; wi < words.size(); ++wi) {
                string const & w = words[wi];
                if (wi > 0 && words[wi - 1] == w) continue;
                bool found = false;
                for (int i = 1; i <= m; ++i) {
                    for (int j = 1; j <= n; ++j) {
                        if (Check(b, N, w, 0, i, j)) {
                            found = true;
                            break;
                        }
                    }
                    if (found) break;
                }
                if (found) result.push_back(w);
            }
            return result;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.