LeetCode 79(Word Search)java

2942 단어 LeetCode
원제: 2D 보드 와 단 어 를 감안 할 때, 격자 에 단어 가 있 는 지 확인 합 니 다.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
2 차원 행렬 과 문자열 을 지정 하여 이 문자열 이 행렬 의 인접 요소 로 배열 되 는 지 판단 합 니 다. 행렬 의 인접 은 상하 좌우 의 인접 을 의미 합 니 다.
사고: 행렬 을 그림 으로 보고 이 문 제 는 이 그림 의 일부 노드 에 대해 깊이 있 는 검색 을 하 는 문제 로 바 뀌 었 다. (일부 노드 는 이 노드 의 값 을 만족 시 키 는 것 이 문자열 의 첫 번 째 문자 와 같다 는 것 을 말한다)
반복 되 는 검색 과 가지치기 의 수 요 를 방지 하기 위해 서, 행렬 의 어떤 위치 가 방문 되 었 는 지 기록 하기 위해 표를 설정 합 니 다. 방문 한 적 이 있 으 면 이 경 로 를 따라 검색 할 수 없습니다.
문자열 에 있 는 모든 문자 가 요구 에 부 합 됩 니 다. 즉, 다음 에 word. charAt (word. length () 을 검색 할 때 검색 이 완료 되 었 습 니 다. 실행 가능 한 해 를 찾 아 전역 변 수 를 진짜 로 설정 한 다음 전역 변 수 를 되 돌려 줍 니 다.
DFS 함수 구축: public void DFS (char [] [] board, boolean [] [] isVisited, String word, int index, int row, int col);
그 중에서 index 는 다음 에 검색 할 색인 을 대표 합 니 다. row 와 col 은 다음 검색 을 대표 합 니 다. 여기 서부 터 시작 합 니 다.
사실은 이것 이 좋 은 쓰기 가 아니 라 더 좋 은 쓰기 방법 은 이 블 로 그 를 참고 할 수 있다 는 것 을 증명 한다.http://blog.csdn.net/happyaaaaaaaaaaa/article/details/50834335
나 도 그 중에서 많은 것 을 얻 었 다.
자신의 코드 를 넣 는 것 이 좋 겠 습 니 다.
/*
* Author:Jassy
* Time:2017/01/04
* Number:LeetCode 79(Word Search)
* Source:https://leetcode.com/problems/word-search/
* Result:AC
* Conclusion:DFS
*/
public class Solution {
    boolean resultFlag=false;
    public boolean exist(char[][] board, String word) {
        int row=board.length;
        int col=board[0].length;
        
        for(int i=0;i=0 && board[row-1][col]==word.charAt(index) && isVisited[row-1][col]==false && resultFlag==false){
            isVisited[row-1][col]=true;
            DFS(board,isVisited,word,index+1,row-1,col);
            isVisited[row-1][col]=false;
        }
        if(row+1<=board.length-1 && board[row+1][col]==word.charAt(index) && isVisited[row+1][col]==false && resultFlag==false){
            isVisited[row+1][col]=true;
            DFS(board,isVisited,word,index+1,row+1,col);
            isVisited[row+1][col]=false;
        }
        if(col-1>=0 && board[row][col-1]==word.charAt(index) && isVisited[row][col-1]==false && resultFlag==false){
            isVisited[row][col-1]=true;
            DFS(board,isVisited,word,index+1,row,col-1);
            isVisited[row][col-1]=false;
        }
        if(col+1<=board[0].length-1 && board[row][col+1]==word.charAt(index) && isVisited[row][col+1]==false && resultFlag==false){
            isVisited[row][col+1]=true;
            DFS(board,isVisited,word,index+1,row,col+1);
            isVisited[row][col+1]=false;
        }
    }
}

좋은 웹페이지 즐겨찾기