וואָרט זוך לעעטקאָדע סאַלושאַן  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַמאַזאָן עפּל בלומבערג ביטעדאַנסע סיסקאָ עבייַ עקספּעדיאַ facebook ינטויט מייקראָסאָפֿט אָראַקל פּינטערעסט ServiceNow Snapchat
אַלגערידאַמז Backtracking קאָדירונג אינטערוויו interviewprep LeetCode LeetCodeSolutions מאַטריץ

פּראָבלעם סטאַטעמענט  

געגעבן אַ mxn ברעט און אַ וואָרט, געפֿינען אויב די וואָרט יגזיסץ אין די גריד.

די וואָרט קענען זיין קאַנסטראַקטאַד פֿון אותיות פון סאַקווענטשאַלי שכייניש סעלז, וווּ "שכייניש" סעלז זענען כאָריזאַנטאַלי אָדער ווערטיקלי ארומיקע. דער זעלביקער בריוו צעל קען ניט זיין געוויינט מער ווי איין מאָל.

בייַשפּיל

board = [["A","B","C","E"],
         ["S","F","C","S"],
         ["A","D","E","E"]],

word = "ABCCED"
true

דערקלערונג:

וואָרט זוך לעעטקאָדע סאַלושאַןשפּילקע

board = [["A","B","C","E"],
         ["S","F","C","S"],
         ["A","D","E","E"]], 

word = "ABCB"
false

צוגאַנג (באַקטראַקינג)  

דאָס איז אַ 2 ד גריד טראַנזווערסאַל פּראָבלעם, וווּ מיר מוזן ויספאָרשן די גריד צו קאָנטראָלירן אויב די געגעבן וואָרט קענען זיין געשאפן מיט שכייניש סעלז פון די גריד. אַנשטאָט פון דורכפירן דפס אויף גאַנץ גריד פּלאַץ, מיר וואָלט נוצן די אָפּטראַקקינג אופֿן מער אָפּטימאַללי. אין באַקקטראַקקינג מעטהאָדס, מיר וועלן בלויז גיין צו דעם וועג צו געפֿינען די לייזונג וואָס גלייַכן אונדזער ציל. אויב מיר וויסן אין עטלעכע פונט אַז די קראַנט וועג וועט נישט פירן צו די לייזונג, מיר וועלן צוריקקריגן און גיין צו די ווייַטער ברירה.

מיר וועלן גיין אַרום די גריד דורך אָפּצייכן די קראַנט צעל אין אונדזער וועג ווי באזוכט אין יעדער שריט. און אין די סוף פון יעדער שריט, מיר וועלן אויך אָפּצייכענען עס אַזוי אַז מיר קענען האָבן אַ ריין שטאַט צו פּרובירן אַן אנדערע ריכטונג.

וואָרט זוך לעעטקאָדע סאַלושאַןשפּילקע

אַלגאָריטהם  

מיר וועלן מאַכן אַ באַקקטראַקקינג פונקציאָנירן וואָס וועט אָנהייבן מיט אַ באַזונדער צעל און אַריבער די שכייניש סעלז פון גריד אין DFS מאָדע. ווייַל די געגעבן וואָרט קענען אָנהייבן פֿון ערגעץ אין די גריד, מיר וואָלט שלייפן אַלע די סעלז פון די גריד און פֿאַר יעדער צעל מיר וועלן רופן די באַקקטראַקקינג פונקציאָנירן סטאַרטינג פון דעם קראַנט צעל.
ווי דעם באַקקטראַקקינג פונקציע איז אַ רעקורסיווע אונטן זענען די סטעפּס צו ינסטרומענט דעם רעקורסיווע פונקציע:

  1. אין די אָנהייב מיר וועלן קאָנטראָלירן אויב מיר האָבן ריטשט די דנאָ אָדער די באַזע פאַל פון די רעקורסיאָן. אויב די וואָרט צו זוכן איז ליידיק אָדער אין אנדערע ווערטער אויב עס איז געפֿונען, מיר קערן אמת.
  2. מיר קאָנטראָלירן אויב אונדזער דרך איז דערווייַל גילטיק אָדער ניט דורך קאָנטראָלירן אויב מיר האָבן אַריבער די גרענעץ פון די גריד, אָדער אויב די קראַנט צעל גלייַכן די ערשטע כאַראַקטער פון די זוכן וואָרט אָדער נישט.
  3. אויב די קראַנט שריט איז גילטיק, צייכן דעם צעל ווי באזוכט. און אָנהייבן צו ויספאָרשן די פיר אינסטרוקציעס דורך רופן די זעלבע באַקטראַקקינג פונקציע פֿאַר רעכט, אַראָפּ, לינקס און אַרויף סעלז.
  4. צום סוף, מיר טאָן ניט באַזוכן דעם קראַנט צעל און געבן די רעזולטאַט פון עקספּלעריישאַן ווי אמת אָדער פאַלש. אויב איינער פון די סאַב-עקספּלעריישאַן רעזולטאַטן אין אמת, מיר קערט אמת פֿון דאָ, אַנדערש קערט פאַלש.
זע אויך
מאָריס טראַווערסאַל

ימפּלעמענטאַטיאָן  

C ++ פּראָגראַם פֿאַר וואָרט זוך לעעטקאָדע סאַלושאַן

#include <bits/stdc++.h>
using namespace std;

int row,col;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

bool backtrack(int i,int j,vector<vector<char>>& board, string word,unsigned int ind)
{
    if(ind>=word.size()) return true;
    if(i<0 || i>=row || j<0 || j>=col || board[i][j]!=word[ind]) return false;

    char t=board[i][j];
    board[i][j]= '#';

    for(int k=0;k<4;k++)
    {
        if(backtrack(i+dx[k],j+dy[k],board,word,ind+1))
            return true;
    }
     board[i][j] = t;
    return false;

}

bool exist(vector<vector<char>>& board, string word) 
{
    row= board.size();
    col= board[0].size();

    for(int i=0;i<row;i++)
        for(int j=0;j<col;j++)
            if(backtrack(i,j,board,word,0))
                return true;
    return false;
}

int main() 
{
     vector<vector<char>> board= {
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
        };
    string word = "ABCCED";
    if(exist(board,word))
        cout<< "true" ;
    else
        cout<< "false" ;
    return 0; 
}
true

Java פּראָגראַם פֿאַר וואָרט זוך לעעטקאָדע סאַלושאַן

class Rextester{
    
  static int row,col;
    static int dx[] = {0, 1, 0, -1};
    static int dy[] = {1, 0, -1, 0};
    
    public static boolean exist(char[][] board, String word)
    {
        row= board.length;
        col= board[0].length;
        
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
                if(backtrack(i,j,board,word,0))
                    return true;
        
        return false;       
    }
    
    static boolean backtrack(int i,int j,char[][] board, String word,int ind)
    {
        if(ind>=word.length()) return true;
        if(i<0 || i>=row || j<0 || j>=col || board[i][j]!=word.charAt(ind)) return false;
        
        char t=board[i][j];
        board[i][j]= '#';
        
        for(int k=0;k<4;k++)
        {
            if(backtrack(i+dx[k],j+dy[k],board,word,ind+1))
                return true;
        }
        
        board[i][j] = t;
        return false;        
    }
    
  public static void main(String args[])
    {
        char[][] board= {
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
        };
        String word = "ABCCED";
    System.out.println(exist(board,word));
    }
}
true

קאַמפּלעקסיטי אַנאַליסיס פֿאַר וואָרט זוך לעעטקאָדע סאַלושאַן  

צייט קאַמפּלעקסיטי

אָ (N * (3 ^ ל)): וווּ N איז די גאַנץ נומער פון סעלז אין די גריד און L איז די לענג פון די געגעבן וואָרט צו זיין געזוכט. טכילעס פֿאַר די באַקקטראַקקינג פונקציע, מיר באַקומען 4 ברירות פֿאַר אינסטרוקציעס, אָבער ווייַטער רידוסט צו 3, ווייַל מיר האָבן שוין באזוכט עס אין פריערדיקן שריט. די טיפעניש פון די רעקורסיווע פונקציע איז גלייַך צו די לענג פון דעם וואָרט (L). דערפֿאַר, אין ערגסט פאַל, די גאַנץ נומער פון פאַנגקשאַנז וועט זיין די נומער פון נאָודז אין 3-נאַרי בוים, וואָס איז וועגן 3 ^ ל.
אין ערגסט פאַל, מיר רופן דעם פֿונקציע סטאַרטינג פֿון N נומער פון סעלז. דעריבער די קוילעלדיק צייט קאַמפּלעקסיטי וועט זיין O (N * (3 ^ L)).

זע אויך
ינסערט ינטערוואַל לעעטקאָדע סאַלושאַן

ספעיס קאַמפּלעקסיטי 

אָ (ל): וווּ L איז די לענג פון דעם געגעבן וואָרט. דער פּלאַץ איז געניצט פֿאַר רעקורסיאָן אָנלייגן.

1