검지 Offer 5: 행렬 의 경로

1. 제목 설명
행렬 에 문자열 의 모든 문 자 를 포함 하 는 경로 가 있 는 지 판단 하기 위해 함 수 를 설계 하 십시오.경 로 는 행렬 의 임 의 한 칸 에서 시작 할 수 있 고 모든 단 계 는 행렬 에서 왼쪽, 오른쪽, 위, 아래 로 한 칸 을 이동 할 수 있다.한 경로 가 행렬 의 한 칸 을 지나 면 이 경 로 는 다시 이 칸 에 들 어 갈 수 없습니다.아래×4 의 행렬 에는 문자열 'bfce' 의 경로 가 포함 되 어 있 습 니 다.
[["a","b","c","e"],["s","f","c","s"],["a","d","e","e"]]
그러나 행렬 에는 문자열 'abfb' 의 경로 가 포함 되 어 있 지 않 습 니 다. 문자열 의 첫 번 째 문자 b 가 행렬 의 첫 번 째 줄 두 번 째 칸 을 차지 한 후에 경 로 는 이 칸 에 다시 들 어 갈 수 없습니다.
 
예시 1:
입력: board = ["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"], word = "ABCCED" 출력: true 예제 2:
입력: board = ["a", "b"], ["c", "d"], word = "abcd" 출력: false
출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof저작권 은 인터넷 에 귀속 된다.상업 전 재 는 정부 에 연락 하여 권한 을 부여 해 주 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.
2. 문제 풀이 사고방식 과 코드
class Solution {
    public boolean exist(char[][] board, String word) {
        if(board==null||board.length==0||word==null||word.length()==0){
            return false;
        }
        char[] words=word.toCharArray();//            
        for(int i=0;i=board.length||j<0||j>=board[0].length||board[i][j]!=words[k]){
            return false;
        }
        //  :1.                        ,
        //        ,         
        if(k==words.length-1){
            return true;
        }
        //    :       ,         ,    temp   
         char temp=board[i][j];
         board[i][j]='/';//  :        ,   '/'    ,          
         boolean res=dfs(board,words,i+1,j,k+1)||
                     dfs(board,words,i-1,j,k+1)||
                     dfs(board,words,i,j+1,k+1)||
                     dfs(board,words,i,j-1,k+1);//         
        board[i][j]=temp;//      ,      
        return res;
    }
}

좋은 웹페이지 즐겨찾기