Leetcode - Word Search I,II

Leetcode - 079. Word Search
私の考え:1.まずboardでヘッダ要素が現れる可能性のある位置を探し、合法的な開始位置ごとにdfs 2を行う.dfsのたびにbacktracingと組み合わせてロールバックを回避

class Solution {
public:

    void dfs(vector>& board, string curs,int row,int col,int m ,int n,bool & status)
    {
        if (status)
            return;
        if (curs.length() <= 0)
        {
            status = true;
            return;
        }
        if (row < 0 || row >= m || col < 0 || col >= n)
        {
            return;
        }
        char ch = board[row][col];
        if (ch != curs[0])
            return;
        string s = curs.substr(1);
        board[row][col] = '.';
        dfs(board, s, row + 1, col, m, n, status);
        dfs(board, s, row - 1, col, m, n, status);
        dfs(board, s, row, col + 1, m, n, status);
        dfs(board, s, row, col - 1, m, n, status);
        board[row][col] = ch;
    }

    bool exist(vector>& board, string word) {
        int m = board.size();
        if (m <= 0)
            return false;
        int n = board[0].size();
        if (n <= 0)
            return false;
        int lens = word.length();
        if (lens <= 0)
            return true;
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                char ch = board[i][j];
                if (ch == word[0])
                {
                    bool status = false;
                    dfs(board, word, i, j, m, n, status);
                    if (status)
                        return true;
                }
            }
        }
        return false;
    }
};

Leetcode - 212. Word Search II
diff:ワードの集合が現れ、条件を満たすワードを結果に追加します.
必要なのは、集合内のwordごとにword searchを呼び出すことです.
Attention:これは比較的堅苦しいやり方で、実測Time~1500 ms程度はこのdfs+backtracingのテーマ内でこのテンプレートの汎用性の書き方に注意しなければならないいくつかの最適化できる細部を紹介するだけです:1.wordsは繰り返す可能性があり、重み付けの過程は最適化することができる.暗黙の詳細(Note:You may assume that all inputs are consist of lowercase letters a-z.)は、本題の最適化の別の方向である.(1.状態2.dfs 3.回復状態を設定する)の典型的な遡及過程において、1つのdfs関数が実行可能な解を得ると、他のdfsをスキップして、直接状態を回復してreturnすることができる

class Solution {
public:

    void dfs(vector>& board, string s, int row, int col, int m, int n,bool & status)
    {
        if (status)
            return;
        if (s.length() <= 0)
        {
            status = true;
            return;
        }
        if (row < 0 || row >= m || col < 0 || col >= n)
            return;
        char ch = board[row][col];
        if (ch != s[0])
            return;
        string str = s.substr(1);
        board[row][col] = '0';
        dfs(board, str, row + 1, col, m, n, status);
        dfs(board, str, row - 1, col, m, n, status);
        dfs(board, str, row, col + 1, m, n, status);
        dfs(board, str, row, col - 1, m, n, status);
        board[row][col] = ch;
    }

    bool helper(vector>& board, string curs)
    {
        int m = board.size();
        if (m <= 0)
            return false;
        int n = board[0].size();
        if (n <= 0)
            return false;
        if (curs.length() <= 0)
            return false;
        char ch = curs[0];
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (ch == board[i][j])
                {
                    bool status = false;
                    dfs(board, curs, i, j, m, n, status);
                    if (status)
                        return true;
                }
            }
        }
        return false;
    }

    vector findWords(vector>& board, vector& words) {
        vector vct;
        int words_len = words.size();
        if (words_len <= 0)
            return vct;
        sort(words.begin(), words.end());
        for (int i = 0;i < words_len;++i)
        {
            if (i > 0 && words[i] == words[i - 1])
                continue;
            if (helper(board, words[i]))
                vct.push_back(words[i]);
        }
        return vct;
    }
};