Java : 2D 배열 (단어 검색)에서 단어를 찾는 방법을 구현하는 방법은 무엇입니까?

Question

2D 보드와 사전의 단어 목록이 주어지면 보드의 모든 단어를 찾고 싶습니다.

각 단어는 연속적으로 인접한 셀의 문자로 구성되어야하며 "인접한"셀은 가로 또는 세로로 인접한 셀입니다. 동일한 문자 셀은 한 단어에 두 번 이상 사용될 수 없습니다.

public List<String> findWords(char[][] board, String[] words) { 
    List<String> res = new ArrayList<>(); 
    TrieNode root = buildTrie(words); 
    for (int i = 0; i < board.length; i++) { 
     for (int j = 0; j < board[0].length; j++) { 
      dfs (board, i, j, root, res); 
     } 
    } 
    return res; 
} 

public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) { 
    char c = board[i][j]; 
    if (c == '#' || p.next[c - 'a'] == null) return; 
    p = p.next[c - 'a']; 
    if (p.word != null) { // found one 
     res.add(p.word); 
     p.word = null;  // de-duplicate 
    } 

    board[i][j] = '#'; 
    if (i > 0) dfs(board, i - 1, j ,p, res); 
    if (j > 0) dfs(board, i, j - 1, p, res); 
    if (i < board.length - 1) dfs(board, i + 1, j, p, res); 
    if (j < board[0].length - 1) dfs(board, i, j + 1, p, res); 
    board[i][j] = c; 
} 

public TrieNode buildTrie(String[] words) { 
    TrieNode root = new TrieNode(); 
    for (String w : words) { 
     TrieNode p = root; 
     for (char c : w.toCharArray()) { 
      int i = c - 'a'; 
      if (p.next[i] == null) p.next[i] = new TrieNode(); 
      p = p.next[i]; 
     } 
     p.word = w; 
    } 
    return root; 
} 

class TrieNode { 
    TrieNode[] next = new TrieNode[26]; 
    String word; 
} 

그리고이 buildTrie(String[] words)에서, 특정 단어의 트라이을 설정 한 후,이 p.word = w;을 수행 예를 들어

, 주어진 words = ["oath","pea","eat","rain"] 보드 =

[ 
    ['o','a','a','n'], 
    ['e','t','a','e'], 
    ['i','h','k','r'], 
    ['i','f','l','v'] 
] 

Return ["eat","oath"]. 

는 다음과 같은 구현을 통해 온 . dfs(...)에서 if (p.word != null)을 확인합니다.

하지만 어떻게 그 다음 p.word는 null 더 이상 아니다는 p.word가 발견 된 단어의 문자의 맨 마지막까지 null 때문이다?

p.word은 색인에 종속되지 않으며 개체 자체와 직접 관련이 있으므로 언제든지 액세스 할 수 있어야합니다. 그러나 단어의 마지막 문자까지 null까지 이해할 수 없습니다. 발견되었다. word는 어디를 노드를 제외하고 모든 노드 기본적으로 null되면, 트라이을 구성하는 동안, 위의 트라이 고려

:

이이 샘플 트라이 당신

Answer 1

감사 끝.

exaple의 경우 위의 trie에 buy을 삽입하면 단어 buy의 모든 문자를 스캔하여 하나의 노드에 배치합니다. 마지막 문자 인 y에 도달하면 buy을 해당 노드의 변수 word에 넣습니다. 따라서 노드가 끝나는 노드를 제외하고 모든 노드의 word은 null과 같습니다.