Java: Wie kann man ein Wort aus einem 2D-Array (Wortsuche) finden?

Question

Angesichts einer 2D-Tafel und einer Liste von Wörtern aus dem Wörterbuch, würde ich gerne alle Wörter in der Tafel finden.

Jedes Wort muss aus Buchstaben der sequenziell benachbarten Zelle aufgebaut werden, wobei "benachbarte" Zellen diejenigen sind, die horizontal oder vertikal benachbart sind. Die gleiche Buchstabenzelle darf nicht mehr als einmal in einem Wort verwendet werden.

Zum Beispiel gegeben words = ["oath","pea","eat","rain"] und Board =

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

Return ["eat","oath"]. 

und kam über die folgende Umsetzung:

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; 
} 

Und in buildTrie(String[] words), nach dem Trie für ein bestimmtes Wort einrichten, es tut p.word = w; . Und in dfs(...) überprüft es für if (p.word != null).

Aber wie kommt es, dass die p.word ist null bis zum allerletzten des Zeichens in einem Wort gefunden wurde, dann p.word ist nicht null mehr?

p.word ist nicht abhängig von irgendwelchen Indizes und es wird direkt auf das Objekt selbst bezogen, so sollte an jedem Punkt zugegriffen werden können, aber ich verstehe einfach nicht, wie es ist null bis zum letzten Zeichen des Wortes wurde gefunden.

Danke

Answer 1

Dies ist ein Beispiel trie:

der oben trie In Anbetracht während der Trie-Konstruktion, die word ist null standardmäßig für jeden Knoten mit Ausnahme des Knotens, auf dem es endet.

Zum Beispiel, beim Einfügen buy in den obigen Trie, scannen wir alle Zeichen des Wortes buy und legen Sie es pro einem Knoten. Und wenn wir das letzte Zeichen y erreichen, setzen wir buy in word Variable dieses Knotens. Deshalb finden Sie jeden anderen Knoten word gleich null mit Ausnahme des Knotens, wo es endet.