単語検索Ⅱ

問題

直感: 単語配列内に存在する (グリッド/ボード上の) 単語を、上下左右に移動して見つけなければなりません。
トラバースはバックトラッキング
を使用して実行できます。 単語の検索には trie を利用できます。これは、接頭辞がツリー内に存在するかどうかを確認することで、早期の識別にも役立ちます。これは、ボードの不必要な走査を避けるためです(つまり、ボードを走査しても意味がありません。接頭辞がトライに存在しない場合、その接頭辞を使用する文字列または単語形式もトライに存在しません)

アプローチ: すべての単語 [] をトライに配置します。次に、各セル (i,j) についてボードを横断し、4 方向すべてに進み、さまざまな文字列を形成します。リスト内のトライに存在する文字列。

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        int max = 0;
        Trie t = new Trie();
        for (String w : words) {
            t.insert(w);
        }

        int arr[][] = new int[board.length][board[0].length];
        StringBuilder str = new StringBuilder();

        Set<String> list = new HashSet<>();// to have only unique strings/words
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // recursively traverse all the cells to find the words
                traverse(i, j, board, arr, arr.length, arr[0].length, t, str, list);
            }
        }
        return new ArrayList<>(list);
    }

    public void traverse(int i, int j, char b[][], int arr[][], int n, int m, Trie t, StringBuilder str,Set<String> list) {

        str.append(b[i][j]);// add current cell character to form a potential prefix/word
        if (!t.startWith(str.toString())) {//early checking of prefix before moving forward to avoid un-necessary traversal
            str.deleteCharAt(str.length() - 1);
            return;
        }
        if (t.present(str.toString()))
            list.add(str.toString());

        arr[i][j] = 1;// mark current cell visited to avoid visiting the same cell the current recursive call stack

        int dirs[][] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };// left,right,up,down

        for (int dir[] : dirs) {
            int I = i + dir[0];
            int J = j + dir[1];
            if (I < n && J < m && I >= 0 && J >= 0 && arr[I][J] == 0) {
                traverse(I, J, b, arr, n, m, t, str, list);
            }
        }
        arr[i][j] =0;// mark unvisited 
        str.deleteCharAt(str.length()-1);// remove the last added character
    }

}

class Node {

    Node node[] = new Node[26];
    boolean flag;

    public boolean isPresent(char c) {
        return node[c - 'a'] != null;
    }

    public Node get(char c) {
        return node[c - 'a'];
    }

    public void add(char c, Node n) {
        node[c - 'a'] = n;
    }

    public void setFlag() {
        this.flag = true;
    }

    public boolean getFlag() {
        return this.flag;
    }
}

class Trie {
    Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(String s) {
        Node node = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!node.isPresent(c)) {
                node.add(c, new Node());
            }
            node = node.get(c);
        }
        node.setFlag();
    }

    public boolean present(String s) {
        Node node = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!node.isPresent(c)) {
                return false;
            }
            node = node.get(c);
        }
        return node.getFlag();
    }

    public boolean startWith(String s) {
        Node node = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!node.isPresent(c)) {
                return false;
            }
            node = node.get(c);
        }
        return true;
    }
}

以上が単語検索Ⅱの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。