Carian Perkataan II

Masalah

Gerak hati: Memandangkan kita perlu mencari perkataan (di grid/papan) yang terdapat dalam tatasusunan perkataan dengan merentasi dalam fesyen atas/bawah/kiri/kanan.
Traversal boleh dilakukan menggunakan backtracking
Untuk mencari perkataan, kita boleh menggunakan trie, kerana ini juga akan membantu kita dalam mengenal pasti awal dengan menyemak sama ada awalan terdapat dalam pokok itu atau tidak. Ini adalah mengelakkan lintasan papan yang tidak perlu(iaitu tiada guna melintasi papan, jika awalan tidak terdapat dalam trie, maka rentetan atau bentuk perkataan menggunakan awalan juga tidak akan hadir dalam trie)

Pendekatan: Kami akan meletakkan semua perkataan[] dalam trie, kemudian kami akan melintasi papan untuk setiap sel(i,j) dan akan pergi ke semua 4 arah untuk membentuk pelbagai rentetan, dan kami akan meletakkan semua rentetan yang terdapat dalam percubaan dalam senarai.

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

Atas ialah kandungan terperinci Carian Perkataan II. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!