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