Словы пошуку  


Узровень складанасці серада
Часта пытаюцца ў амазонка яблык Bloomberg ByteDance Cisco facebook Спасцігаць інтуітыўна Microsoft Аракул ServiceNow Snapchat
масіў Фанаграмы

Пошук слоў - гэта нешта накшталт загадак пра пошук слоў у пэўны час нашага жыцця. Сёння я прыношу да стала а мадыфікаваны крыжаванкі.

Мае чытачы, напэўна, збянтэжаныя тым, пра што я кажу. Не губляючы больш часу, давайце пяройдзем да вырашэння праблемы

Словы пошукуPin
Невялікі крыжаванка па лініі пошуку слова.

Вы можаце знайсці ўсе словы?

Мы можам пабудаваць слова па вертыкалі альбо гарызанталі суседні слова. загвоздка у тым, што вы не можаце зноў выкарыстоўваць тую ж літару.

Прыклад  

Давайце разгледзім некалькі прыкладаў

Увод: [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E "," E "]]

Слова: "ABCB"

Вынік: праўда

Увядзіце [["A", "B", "C", "E"], ["S", "" F "," C "," S "], [" A "," D "," E "," E "]]

Слова: "ГЛЯДЗІ"

Вынік: праўда

Што мы можам зрабіць?  

Вось некалькі пунктаў, па якіх мы выконваем пошук слоў у галаваломцы.

  • Пракруціце матрыцу і пачніце з таго месца, дзе мы знаходзім першую літару
  • Няхай бягучы сімвал будзе cur і праверце радок рэкурсіўна з дапамогай ДФС.
  • Калі мы даходзім да канца слова, гэта значыць маем знайшоў усіх герояў у матрыцы мы вяртанне праўда
  • Праверце кожны сімвал матрыцы
  • Калі сімвал у слове, паглядзіце ў клеткі
    • Гарызантальна наперадзе
    • Гарызантальна ззаду
    • Вертыкальна ўверсе
    • Вертыкальна ўнізе
    • Калі які-небудзь з званкоў вярнуцца праўдай. Ага! мы знайшлі гэтае слова. Нам больш не трэба шукаць
    • Вярнуць АБО з усіх званкоў
  • Калі персанаж не знойдзены, мы вяртаемся ілжывы 
  • Для таго, каб мы не вярталіся да адной і той жа ячэйкі, мы маскіруем значэнне кожнай ячэйкі заблуджаным сімвалам
Глядзіце таксама
N каралева праблема

Давайце зразумеем гэта лепш з дапамогай фрагмента кода

Код Java для пошуку слоў  

class Solution
{
    boolean trav(char[][] board,int cur,int i,int j,String word)
    {
       //If we have found all the characters
       if(cur>=word.length())
            return true;
       //In case the character does not match/we go out of the board
       if(i<0 || j<0 || i>=board.length || j>=board[i].length || 
          board[i][j]!=word.charAt(cur))
            return false;
        //Masking our board to prevent repetitive calls
        char temp=board[i][j];
        board[i][j]='*';
        boolean ans=(trav(board,cur+1,i+1,j,word) || trav(board,cur+1,i,j+1,word)
                     || trav(board,cur+1,i-1,j,word) || trav(board,cur+1,i,j-1,word));
        board[i][j]=temp;
            return ans;   
    }
    public boolean exist(char[][] board, String word) 
    {
        boolean ans=false;
        for(int i=0;i<board.length;i++)
        {
            for(int j=0;j<board[i].length;j++)
            {
                //We start checking from where we find the first character
                if(board[i][j]==word.charAt(0) && trav(board,0,i,j,word))
                {
                    return true;
                }
            }
        }
        return false;
    }
}

C ++ код для пошуку слоў  

{
public:
    bool trav(vector<vector<char>>& board,int cur,int i,int j,string word)
    {
       if(cur>=word.length())
            return true;
       if(i<0 || j<0 || i>=board.size() || j>=board[i].size() || 
          board[i][j]!=word[cur])
            return false;
        char temp=board[i][j];
        board[i][j]='*';
        bool ans=(trav(board,cur+1,i+1,j,word) || trav(board,cur+1,i,j+1,word)
                     || trav(board,cur+1,i-1,j,word) || trav(board,cur+1,i,j-1,word));
        board[i][j]=temp;
            return ans;   
    }
public:
    bool exist(vector<vector<char>>& board, string word)
    {
     for(int i=0;i<board.size();i++)
     {
     for(int j=0;j<board[i].size();j++)
     {
     if(board[i][j]==word[0] && trav(board,0,i,j,word))
     {
     return true;
     }
     }
     }
    return false;   
    }
};
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]

ABCB
true

Аналіз складанасці  

Складанасць часу: O (m * n * l)

дзе,

m = Даўжыня матрыцы

n = шырыня матрыцы

l = Даўжыня слова, дадзенага ў задачы пошуку слоў.

Як?

  • Мы праходзім па ўсёй дошцы, спрабуючы высветліць першую літару слова
    • У горшым выпадку мы можам абысці ўсю дошку, не націснуўшы першага знака
    • Затым мы шукаем бліжэйшыя сімвалы, пакуль не патрапім на наступнага
      • Такім чынам, мы праходзім праз усё слова
      • Часавая складанасць гэтага = O (L)
    • Гэтая аперацыя O (L) можа быць выклікана кожны раз у знешнім цыкле O (M). Складанасць часу да гэтага часу O (M * L)
  • Вышэйапісаныя аперацыі выконваюцца ў цыкле O (N)
  • Тры завесы аб'ядноўваюцца, каб скласці час = O (M * N * L)