단어 검색 II

문제

직관: 위/아래/왼쪽/오른쪽 방식으로 탐색하여 단어 배열에 있는 단어(그리드/보드에서)를 찾아야 하기 때문입니다.
순회는 역추적을 사용하여 수행할 수 있습니다
단어 검색을 위해 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;
    }
}

위 내용은 단어 검색 II의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!