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

• ``````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;
}
};
``````

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