ການຊອກຫາ ຄຳ ສັບ Leetcode Solution


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon ຈາກຫນາກແອບເປີ Bloomberg ByteDance Cisco eBay Expedia ເຟສບຸກ Intuit Microsoft Oracle Pinterest ServiceNow SnapChat
Backtracking ມາຕຣິກເບື້ອງ

ຖະແຫຼງການບັນຫາ

ໃຫ້ຄະນະ mxn ແລະ ຄຳ, ຊອກຫາວ່າ ຄຳ ສັບນັ້ນມີຢູ່ໃນຕາຂ່າຍໄຟຟ້າຫລືບໍ່.

ຄຳ ສັບດັ່ງກ່າວສາມາດສ້າງຂື້ນຈາກຕົວອັກສອນຂອງຈຸລັງທີ່ຢູ່ຕິດກັນຕາມ ລຳ ດັບ, ບ່ອນທີ່ຈຸລັງ“ ຕິດກັນ” ຕັ້ງຢູ່ຕາມແນວນອນຫລືແນວຕັ້ງໃກ້ຄຽງ. ຫ້ອງໂທລະສັບດຽວກັນອາດຈະບໍ່ຖືກ ນຳ ໃຊ້ຫຼາຍກ່ວາ ໜຶ່ງ ຄັ້ງ.

ຍົກຕົວຢ່າງ

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

word = "ABCCED"
true

ຄໍາອະທິບາຍ:

ການຊອກຫາ ຄຳ ສັບ Leetcode Solution

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

word = "ABCB"
false

ວິທີການ (Backtracking)

ນີ້ແມ່ນບັນຫາເສັ້ນທາງ 2D ຕາຂ່າຍໄຟຟ້າ, ບ່ອນທີ່ພວກເຮົາຕ້ອງ ສຳ ຫຼວດຕາຂ່າຍໄຟຟ້າເພື່ອກວດກາເບິ່ງວ່າ ຄຳ ສັບທີ່ໃຫ້ໄວ້ນັ້ນສາມາດສ້າງຂື້ນໄດ້ໂດຍໃຊ້ຈຸລັງທີ່ຢູ່ຕິດກັນຂອງຕາຂ່າຍໄຟຟ້າ. ແຕ່ແທນທີ່ຈະປະຕິບັດ DFS ໃນພື້ນທີ່ຂອງຕາຂ່າຍໄຟຟ້າທັງ ໝົດ, ພວກເຮົາຈະໃຊ້ວິທີການສະແດງແບບແຜນພາບທີ່ດີທີ່ສຸດ. ໃນວິທີການ backtracking ພວກເຮົາພຽງແຕ່ຈະໄປເສັ້ນທາງນັ້ນເພື່ອຊອກຫາວິທີແກ້ໄຂທີ່ກົງກັບຈຸດປະສົງຂອງພວກເຮົາ. ຖ້າພວກເຮົາຮູ້ໃນບາງຈຸດວ່າເສັ້ນທາງໃນປະຈຸບັນຈະບໍ່ ນຳ ໄປສູ່ການແກ້ໄຂ, ຫຼັງຈາກນັ້ນພວກເຮົາກໍ່ຈະຕອບໂຕ້ຄືນແລະໄປທາງເລືອກຕໍ່ໄປ.

ພວກເຮົາຈະໄປປະມານຕາຂ່າຍໄຟຟ້າໂດຍການ ໝາຍ ຫ້ອງປະຈຸບັນຢູ່ໃນເສັ້ນທາງຂອງພວກເຮົາດັ່ງທີ່ໄດ້ໄປຢ້ຽມຢາມໃນແຕ່ລະບາດກ້າວ. ແລະໃນຕອນທ້າຍຂອງແຕ່ລະບາດກ້າວພວກເຮົາຍັງຈະຍົກເລີກການ ໝາຍ ເພື່ອພວກເຮົາຈະມີສະພາບທີ່ສະອາດເພື່ອທົດລອງທິດທາງອື່ນ.

ການຊອກຫາ ຄຳ ສັບ Leetcode Solution

ລະບົບວິເຄາະ

ພວກເຮົາຈະເຮັດ ໜ້າ ທີ່ຕອບໂຕ້ຄືນເຊິ່ງຈະເລີ່ມຕົ້ນດ້ວຍຈຸລັງເສພາະເຈາະຈົງແລະຂ້າມຈຸລັງທີ່ຢູ່ຕິດກັນຂອງຕາຂ່າຍໄຟຟ້າໃນແບບ DFS. ເນື່ອງຈາກວ່າ ຄຳ ສັບທີ່ໃຫ້ໄວ້ສາມາດເລີ່ມຕົ້ນໄດ້ຈາກທຸກບ່ອນໃນຕາຂ່າຍໄຟຟ້າ, ພວກເຮົາຈະລວບລວມທຸກໆຈຸລັງຂອງຕາຂ່າຍໄຟຟ້າແລະ ສຳ ລັບແຕ່ລະຫ້ອງແຕ່ລະຫ້ອງພວກເຮົາຈະໂທຫາ ຕຳ ແໜ່ງ backtracking ເລີ່ມຈາກຫ້ອງປະຈຸບັນນີ້
ໃນຖານະເປັນຫນ້າທີ່ backtracking ນີ້ແມ່ນ ຮຽກຮ້ອງ ຫນ້າທີ່, ຂ້າງລຸ່ມນີ້ແມ່ນບາດກ້າວໃນການຈັດຕັ້ງປະຕິບັດ ໜ້າ ທີ່ນີ້:

  1. ໃນຕອນເລີ່ມຕົ້ນພວກເຮົາຈະກວດເບິ່ງວ່າພວກເຮົາໄດ້ໄປຮອດຈຸດລຸ່ມຫລືກໍລະນີພື້ນຖານຂອງການເອີ້ນຄືນ. ຖ້າວ່າ ຄຳ ທີ່ຕ້ອງການຄົ້ນຫາແມ່ນຫວ່າງເປົ່າຫລືເປັນອີກ ຄຳ ສັບ ໜຶ່ງ ຖ້າມັນພົບເຫັນ, ພວກເຮົາກໍ່ກັບຄືນມາເປັນຄວາມຈິງ.
  2. ພວກເຮົາກວດເບິ່ງວ່າເສັ້ນທາງຂອງພວກເຮົາແມ່ນຖືກຕ້ອງຫຼືບໍ່ໃນປະຈຸບັນໂດຍການກວດສອບວ່າພວກເຮົາໄດ້ຂ້າມເຂດແດນຂອງຕາຂ່າຍໄຟຟ້າຫລືຖ້າວ່າຫ້ອງປະຈຸບັນກົງກັບລັກສະນະ ທຳ ອິດຂອງ ຄຳ ຄົ້ນຫາຫລືບໍ່.
  3. ຖ້າຂັ້ນຕອນໃນປະຈຸບັນແມ່ນຖືກຕ້ອງແລ້ວໃຫ້ ໝາຍ ໃສ່ຫ້ອງນີ້ວ່າທ່ານໄດ້ໄປຢ້ຽມຢາມ. ແລະເລີ່ມຕົ້ນຄົ້ນຫາສີ່ທິດທາງໂດຍການໂທຫາຟັງຊັນ backtracking ດຽວກັນ ສຳ ລັບຫ້ອງຂວາ, ລຸ່ມ, ຊ້າຍແລະຂຶ້ນ.
  4. ໃນທີ່ສຸດພວກເຮົາບໍ່ໄປຢ້ຽມຢາມຫ້ອງປະຈຸບັນແລະສົ່ງຜົນໄດ້ຮັບຈາກການ ສຳ ຫຼວດວ່າເປັນຄວາມຈິງຫຼືບໍ່ຖືກຕ້ອງ. ຖ້າມີການ ສຳ ຫຼວດຍ່ອຍໃດ ໜຶ່ງ ເກີດຜົນໃນຄວາມຈິງແລ້ວພວກເຮົາກໍ່ກັບມາຈາກທີ່ນີ້ຖ້າບໍ່ດັ່ງນັ້ນກໍ່ຈະສົ່ງຄືນບໍ່ຖືກຕ້ອງ.

ການປະຕິບັດ

ໂຄງການ C ++ ສຳ ລັບການຊອກຫາ ຄຳ ສັບ Leetcode Solution

#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 Program ສຳ ລັບການຊອກຫາ ຄຳ ສັບ Leetcode Solution

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

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການຊອກຫາ ຄຳ ສັບ Leetcode Solution

ຄວາມສັບສົນເວລາ

O (N * (3 ^ L)): ບ່ອນທີ່ N ແມ່ນ ຈຳ ນວນຈຸລັງທັງ ໝົດ ໃນຕາຂ່າຍໄຟຟ້າແລະ L ແມ່ນຄວາມຍາວຂອງ ຄຳ ທີ່ໃຫ້ໄວ້ເພື່ອຄົ້ນຫາ. ສຳ ລັບຟັງຊັນ backtracking ໃນເບື້ອງຕົ້ນພວກເຮົາໄດ້ຮັບ 4 ຕົວເລືອກ ສຳ ລັບທິດທາງແຕ່ຕໍ່ໄປມັນຫຼຸດລົງເປັນ 3 ດັ່ງທີ່ພວກເຮົາໄດ້ໄປເບິ່ງມັນແລ້ວໃນບາດກ້າວກ່ອນ ໜ້າ ຄວາມເລິກຂອງ ໜ້າ ທີ່ການເອີ້ນຄືນນີ້ຈະເທົ່າກັບຄວາມຍາວຂອງ ຄຳ (L). ເພາະສະນັ້ນໃນກໍລະນີທີ່ບໍ່ດີທີ່ສຸດ ຈຳ ນວນການຮຽກຮ້ອງການເຮັດວຽກທັງ ໝົດ ຈະເປັນ ຈຳ ນວນຂໍ້ຂອງຕົ້ນໄມ້ 3 ນາລີ, ເຊິ່ງປະມານ 3 ^ ລານ.
ໃນກໍລະນີທີ່ຮ້າຍແຮງທີ່ສຸດພວກເຮົາເອີ້ນວ່າຫນ້າທີ່ນີ້ເລີ່ມຕົ້ນຈາກຈໍານວນຈຸລັງ N. ເພາະສະນັ້ນ, ຄວາມສັບສົນທີ່ໃຊ້ເວລາໂດຍລວມຈະເປັນ O (N * (3 ^ L)).

ຄວາມສັບສົນໃນອະວະກາດ 

O (L): ບ່ອນທີ່ L ແມ່ນຄວາມຍາວຂອງ ຄຳ ທີ່ໃຫ້. ພື້ນທີ່ນີ້ແມ່ນໃຊ້ ສຳ ລັບການເອີ້ນຄືນ.