4 x 4 글자 보드와 단어 목록이 있다고 가정하고 단어당 최대 한 번 셀을 사용하여 인접한 문자 시퀀스에 의해 보드에서 생성될 수 있는 최대 단어 수를 찾아야 합니다(그러나 우리는 다른 말로 셀을 재사용할 수 있음). 위, 아래, 왼쪽, 오른쪽 또는 대각선 방향으로 이동할 수 있습니다.
따라서 입력이 다음과 같으면
| m | b | f | d |
| x | a | y | a |
| t | z | t | r |
| q | q | q |
단어 =["bat", "far", "mat"]이면 출력은 3이 됩니다. mat [0,1] → [1,1] → [2,0], bat [0, 2] → [1,1] → [2,2], 그리고 멀리 [0,2] → [1,3] → [2,3].
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
N :=A의 행 개수, M :=A 크기의 열 개수
-
시도 :=새 지도
-
단어의 각 단어에 대해 수행
-
현재 :=시도
-
단어의 각 c에 대해 수행
-
c가 현재 상태이면
-
현재 :=현재[c]
-
-
그렇지 않으면
-
현재[c] :=새 지도
-
현재 :=현재[c]
-
-
-
현재["*"] :=참
-
-
답변 :=0
-
dfs() 함수를 정의합니다. x, y, d
가 필요합니다. -
"*"가 d에 있으면
-
d["*"]
제거 -
ans :=ans + 1
-
-
온도 :=A[x, y]
-
A[x, y] :="#"
-
[x - 1, x, x + 1]의 각 항목 i에 대해 수행
-
[y - 1, y, y + 1]의 각 항목 j에 대해 수행
-
i와 j가 행렬의 범위에 있고 A[i, j]가 d에 있으면
-
dfs(i, j, d[A[i, j]])
-
-
-
-
A[x, y] :=온도
-
주요 방법에서 다음을 수행하십시오 -
-
범위 0에서 N까지의 i에 대해 수행
-
0에서 M 범위의 j에 대해 수행
-
A[i][j]가 트라이에 있으면
-
dfs(i, j, trie[A[i, j]])
-
-
-
-
반환
예제(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class 솔루션:def solve(self, A, words):N =len(A) M =len(A[0]) trie =dict() for word in words:current =trie for c in word:if c in current:current =current[c] else:current[c] =dict() current =current[c] current["*"] =True ans =0 def dfs(x, y, d):nonlocal ans if "*" in d:del d["*"] ans +=1 temp =A[x][y] A[x][y] ="#" for i in [x - 1, x, x + 1 ]:[y - 1, y, y + 1]의 j에 대해:0 <=i입력
<미리>[["m", "b", "f", "d"],["x", "a", "y", "a"],["t", "z", " t", "r"],["s", "q", "q", "q"] ],["bat", "far", "mat"]
출력
3