DFS Soln to Word Проблема поиска в Leetcode - PullRequest
Новая
       21

DFS Soln to Word Проблема поиска в Leetcode

0 голосов
/ 23 марта 2020

Ссылка на проблему: https://leetcode.com/problems/word-search/

Я понятия не имею, почему, но приведенный ниже пример не проходит несколько тестовых случаев. Пожалуйста, помогите!

Моя идея состояла в том, чтобы продолжать поиск следующей буквы слова, чтобы найти ее в левом, правом, верхнем и нижнем элементах, пока я не найду все буквы. Для реализации этой идеи я использовал DFS.

Мое решение: 

class Solution {
public:
    int vis[201][201];
    int c=0;
    void dfs(vector<vector<char>>& board, int i, int j, int m, int n, string &word, int k)
    {
        if(k==word.size())
        {
            c=1;
            return;
        }
        if(i!=m-1&&board[i+1][j]==word[k]&&vis[i+1][j]==0)
        {
            vis[i+1][j]=1;
            dfs(board,i+1,j,m,n,word,k+1);

        }
        if(j!=n-1&&board[i][j+1]==word[k]&&vis[i][j+1]==0)
        {   
          vis[i][j+1]=1;
          dfs(board,i,j+1,m,n,word,k+1);
        }
        if(i!=0&&board[i-1][j]==word[k]&&vis[i-1][j]==0)
        {   
            vis[i-1][j]=1;
            dfs(board,i-1,j,m,n,word,k+1);
        }

        if(j!=0&&board[i][j-1]==word[k]&&vis[i][j-1]==0)
        {
            vis[i][j-1]=1;
            dfs(board,i,j-1,m,n,word,k+1);
        }


    }

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

1 Ответ

0 голосов
/ 23 марта 2020

В функции bool существуют (...), я полагаю, вам нужно сбрасывать массив vis 2d на каждой итерации.

Поскольку предыдущий поиск dfs, но безуспешно, это посещение может повлиять на следующий поиск.

А также некоторые предложения по улучшению, вы можете добавить условие c == 1 в

if (board [i] [j] == word [0] && vis [i] [j] == 0)

или внешняя область действия

, потому что нас интересует только, найдено слово или нет.

Мы должны избегать вызова рекурсивной функции, потому что это стоит очень дорого

================= *

Я прочитал Снова кодируйте и обнаружите, что функция dfs не является dfs и действует больше как bfs. Я предполагаю фундаментальную проблему оттуда.

А также существует проблема ограничения времени при посещении 4-х направлений.

  1. исправление dfs

В fuction dfs ваш исходный код похож на 

    void dfs(vector<vector<char>>& board, int i, int j, int m, int n, string &word, int k)
    {
        if(k==word.size())
        {
            c=1;
            return;
        }
        if(i!=m-1&&board[i+1][j]==word[k]&&vis[i+1][j]==0)
        {
            vis[i+1][j]=1;
            dfs(board,i+1,j,m,n,word,k+1);
        }

        if(j!=n-1&&board[i][j+1]==word[k]&&vis[i][j+1]==0)
        {   
          vis[i][j+1]=1;
          dfs(board,i,j+1,m,n,word,k+1);
        }
        ......

Предположим, что у нас есть карта символов, подобная

\ 0 1 2

0 xab

1 c bb

, и мы нужно найти "abbb c"

, как вы можете видеть, мы можем найти "abbb c", посетив

(0, 1) -> (0, 2) - > (1, 2) -> (1, 1) -> (1, 0) [при условии, что верхний левый индекс равен (0, 0)]

, но, следуя вашему коду, вы сначала заходите вниз, поэтому ( 1, 1) помечен как посещение, поэтому вы не можете найти «abbb c»

, чтобы исправить это, вы сбросили отметку посещения, когда завершена рекурсия sh. 

        if(i!=m-1&&board[i+1][j]==word[k]&&vis[i+1][j]==0)
        {
            vis[i+1][j]=1;
            dfs(board,i+1,j,m,n,word,k+1);
            vis[i+1][j]=0; // this should add to every direction.
        }

также Как я уже говорил, в существующей функции вы должны сбросить карту посещений при вызове dfs

ограничение по времени.

Невозможно остановить dfs, когда переменная c уже стала 1.

Например, вам повезло, и вы нашли слово по посещение ВНИЗ -> ВНИЗ -> ВНИЗ -> ВНИЗ.

Но согласно вашему коду программа должна перейти по следующему возможному пути ВПРАВО -> ~~~, ВВЕРХ -> ~~~, ВЛЕВО -> ~~~.

, чтобы избежать этого, вы должны вставить выражение возврата между вызовами рекурсии. 

        if(i!=m-1&&board[i+1][j]==word[k]&&vis[i+1][j]==0)
        {
            ~~~
        }

        if (c == 1) return;

        if(j!=n-1&&board[i][j+1]==word[k]&&vis[i][j+1]==0)
        {   
            ~~~
        }

Это сокращает время, не вызывая ненужную рекурсию.

...