-1

想知道我的代码哪里出错了，请帮助我获得预期的输出。提前致谢。##Word 搜索 II## 来自 leetcode：

代码：

class Solution {

    public List<String> findWords(char[][] board, String[] words) {

        List<String> result = new ArrayList<String>();

        if (board.length <= 0 || words.length <= 0) {
            return result;
        }

        for (int i = 0; i < words.length; i++) {

            if (result.contains(words[i])) {
                continue;
            }

            for (int j = 0; j < board.length; j++) {

                for (int k = 0; k < board[0].length; k++) {

                    if (result.contains(words[i])) {
                        break;
                    }

                    if (words[i].charAt(0) == board[j][k]) {

                        boolean isVisited[][] = new boolean[board.length][board[0].length];
                        for (boolean a[] : isVisited) {
                            Arrays.fill(a, false);
                        }
                        if (dfs(j, k, words[i], 0, board, isVisited)) {
                            result.add(words[i]);

                        }

                    }
                }
            }
        }

        return result;
    }

    boolean dfs(int row, int col, String word, int index, char[][] board, boolean[][] isVisited) {

        if (index == word.length()) {
            return true;
        } else if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || isVisited[row][col] || board[row][col] != word.charAt(index)) {
            return false;
        } else {
            System.out.println(word.charAt(index) + " = " + index);
            isVisited[row][col] = true;
            return dfs(row + 1, col, word, index + 1, board, isVisited)
                    || dfs(row, col + 1, word, index + 1, board, isVisited)
                    || dfs(row - 1, col, word, index + 1, board, isVisited)
                    || dfs(row, col - 1, word, index + 1, board, isVisited);

        }
    }

}

输入：

[["a","b","c"],["a","e","d"],["a","f","g"]]
["abcdefg","gfedcbaaa","eaabcdgfa","befa","dgc","ade"]

我的输出：

["abcdefg","gfedcbaaa","befa"]

预期的：

["abcdefg","befa","eaabcdgfa","gfedcbaaa"]
4

1 回答 1

0

很难找到你的错误，同样对于这个问题，尝试使用 Trie 数据结构实现你的深度优先搜索：

class Solution {
    public List<String> findWords(char[][] grid, String[] words) {
        List<String> foundWords = new ArrayList<>();
        Node root = Trie(words);
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[0].length; col++) {
                depthFirstSearch(grid, row, col, root, foundWords);
            }
        }
        return foundWords;
    }

    public void depthFirstSearch(char[][] grid, int row, int col, Node curr, List<String> foundWords) {
        char character = grid[row][col];
        if (character == '#' || curr.next[character - 'a'] == null)
            return;
        curr = curr.next[character - 'a'];
        if (curr.isWord != null) {
            foundWords.add(curr.isWord);
            curr.isWord = null;
        }

        grid[row][col] = '#';
        if (row > 0)
            depthFirstSearch(grid, row - 1, col, curr, foundWords);
        if (col > 0)
            depthFirstSearch(grid, row, col - 1, curr, foundWords);
        if (row < grid.length - 1)
            depthFirstSearch(grid, row + 1, col, curr, foundWords);
        if (col < grid[0].length - 1)
            depthFirstSearch(grid, row, col + 1, curr, foundWords);
        grid[row][col] = character;
    }

    public Node Trie(String[] words) {
        Node root = new Node();
        for (String word : words) {
            Node curr = root;
            for (char character : word.toCharArray()) {
                int row = character - 'a';
                if (curr.next[row] == null)
                    curr.next[row] = new Node();
                curr = curr.next[row];
            }
            curr.isWord = word;
        }
        return root;
    }

    class Node {
        Node[] next = new Node[26];
        String isWord;
    }
}

这是 LeetCode 的解决方案之一：

class TrieNode {
  HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
  String word = null;
  public TrieNode() {}
}

class Solution {
  char[][] _board = null;
  ArrayList<String> _result = new ArrayList<String>();

  public List<String> findWords(char[][] board, String[] words) {

    // Step 1). Construct the Trie
    TrieNode root = new TrieNode();
    for (String word : words) {
      TrieNode node = root;

      for (Character letter : word.toCharArray()) {
        if (node.children.containsKey(letter)) {
          node = node.children.get(letter);
        } else {
          TrieNode newNode = new TrieNode();
          node.children.put(letter, newNode);
          node = newNode;
        }
      }
      node.word = word;  // store words in Trie
    }

    this._board = board;
    // Step 2). Backtracking starting for each cell in the board
    for (int row = 0; row < board.length; ++row) {
      for (int col = 0; col < board[row].length; ++col) {
        if (root.children.containsKey(board[row][col])) {
          backtracking(row, col, root);
        }
      }
    }

    return this._result;
  }
  
  private void backtracking(int row, int col, TrieNode parent) {
    Character letter = this._board[row][col];
    TrieNode currNode = parent.children.get(letter);

    // check if there is any match
    if (currNode.word != null) {
      this._result.add(currNode.word);
      currNode.word = null;
    }

    // mark the current letter before the EXPLORATION
    this._board[row][col] = '#';

    // explore neighbor cells in around-clock directions: up, right, down, left
    int[] rowOffset = {-1, 0, 1, 0};
    int[] colOffset = {0, 1, 0, -1};
    for (int i = 0; i < 4; ++i) {
      int newRow = row + rowOffset[i];
      int newCol = col + colOffset[i];
      if (newRow < 0 || newRow >= this._board.length || newCol < 0
          || newCol >= this._board[0].length) {
        continue;
      }
      if (currNode.children.containsKey(this._board[newRow][newCol])) {
        backtracking(newRow, newCol, currNode);
      }
    }

    // End of EXPLORATION, restore the original letter in the board.
    this._board[row][col] = letter;

    // Optimization: incrementally remove the leaf nodes
    if (currNode.children.isEmpty()) {
      parent.children.remove(letter);
    }
  }
}

参考

  • 有关其他详细信息，您可以查看讨论板。那里有很多公认的解决方案、解释、各种语言的高效算法以及时间/空间复杂度分析。
于 2020-06-30T19:51:55.503 回答