검지 Offer 5: 행렬 의 경로
행렬 에 문자열 의 모든 문 자 를 포함 하 는 경로 가 있 는 지 판단 하기 위해 함 수 를 설계 하 십시오.경 로 는 행렬 의 임 의 한 칸 에서 시작 할 수 있 고 모든 단 계 는 행렬 에서 왼쪽, 오른쪽, 위, 아래 로 한 칸 을 이동 할 수 있다.한 경로 가 행렬 의 한 칸 을 지나 면 이 경 로 는 다시 이 칸 에 들 어 갈 수 없습니다.아래×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;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
최소 k 개수 자바최소 k 개수 자바 제목 설명 은 n 개의 정 수 를 입력 하여 그 중에서 가장 작은 K 개 수 를 찾 아 냅 니 다.예 를 들 어 4, 5, 1, 6, 2, 7, 3, 8 이라는 8 개의 숫자 를 입력 하면 가장 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.