boggle game

import java.util.*;

/**
 * 注意: 如果字典里的词能重复放的话,主函数(findMostWords)要用list而不是set
 *       如果字典里的词只能放一次,主函数要用set而不是list
 */

public class BoggleGame {
  public static char[][] stringArrToBoard (String[] input) {
    int rows = input.length;
    int cols = input[0].length();
    char[][] board = new char[rows][cols];
    for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
        board[i][j] = input[i].charAt(j);
      }
    }
    return board;
  }

  public static void main(String[] args) {
    String[] input = {"aaaa", "aaaa", "aaaa"};
    //String[] dict = {"aaa", "aa", "a", "aaaa", "aaaaa", "aaaaaa"};
    String[] dict = {"aa", "a", "aaaa", "aaaaa", "aaaaaa"};

//        String[] input =
//                {
//                "aple",
//                "ppig",
//                "plex",
//                "agel"
//                };
//        String[] dict = {"apple", "plex", "pig", "page", "age"};
    BoggleGame sol = new BoggleGame();
    sol.boggle(stringArrToBoard(input), dict);
  }

  class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isWord;
  }

  class Trie {
    TrieNode root;

    public Trie (TrieNode root) {
      this.root = root;
    }

    public void addWord(String word) {
      TrieNode curr = root;
      for (char c : word.toCharArray()) {
        if (curr.children[c - 'a'] == null) {
          curr.children[c - 'a'] = new TrieNode();
        }
        curr = curr.children[c - 'a'];
      }
      curr.isWord = true;
    }
  }
  static int[] dx = {1, -1, 0 , 0};
  static int[] dy = {0, 0, 1, -1};
  private char[][] board;
  private String[] dict;
  private boolean[][] visited;
  private Trie trie;

  public int boggle (char[][] board, String[] dict) {
    this.board = board;
    this.dict = dict;
    buildTrie();
    visited = new boolean[board.length][board[0].length];
    List<String> res = new ArrayList<>();
    findMostWords(res, new ArrayList<>(), 0, 0, trie.root);

    System.out.println("can fit: " + res.size() + " words");
    System.out.println("Words: ");
    for (String str : res) {
      System.out.print(str + ", ");
    }
    return res.size();
  }

  public void findMostWords (List<String> res, List<String> curWords, int x, int y, TrieNode curNode) {
    int m = board.length;
    int n = board[0].length;
    // 遍历整个board, 以每个cell为起点找各自的最大集合
    for (int i = x; i < m; i++) {
      for (int j = y; j < n; j++) {
        List<List<Integer>> nextWords = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        // 相当于word search II, 找到以这个点为起点能找到所有words
        findNextWords(nextWords, path, i, j, curNode);
        // 把每个词放入都试下
        for (List<Integer> nextWordIdx : nextWords) {
          String nextWord = "";
          // 把这个词的路径标记已访问
          for (int idx : nextWordIdx) {
            int row = idx / n;
            int col = idx % n;
            visited[row][col] = true;
            nextWord += board[row][col];
          }
          // 把这个词放入集合
          curWords.add(nextWord);
          if (curWords.size() > res.size()) {
            res.clear();
            res.addAll(curWords);
          }

          // 以此点为起点找这个平行世界的最大集合
          findMostWords(res, curWords, i, j, curNode);//不要写成x,y!!!!

          for (int idx : nextWordIdx) {
            int row = idx / n;
            int col = idx % n;
            visited[row][col] = false;
          }
          curWords.remove(curWords.size() - 1);
        }
      }
      y = 0;
    }
  }

  // 相当于word search II
  public void findNextWords(List<List<Integer>> words, List<Integer> path, int x, int y, TrieNode curNode) {
    if (!canGo(x, y) || curNode.children[board[x][y] - 'a'] == null) {
      return;
    }

    char c = board[x][y];
    curNode = curNode.children[c - 'a'];

    path.add(x * board[0].length + y);
    // find a word
    if (curNode.isWord) {//这里也要注意,上面换了curNode才能直接用isWord
      words.add(new ArrayList<>(path));
//      path.remove(path.size () - 1);//注意别漏
//      return;//注意这里没有也能解出,面试时候可以不写
    }
    visited[x][y] = true;
    for (int i  = 0; i < 4; i++) {
      int xx = x + dx[i];
      int yy = y + dy[i];
      findNextWords(words, path, xx, yy, curNode);
    }
    visited[x][y] = false;
    path.remove(path.size() - 1);//别漏
  }

  private boolean canGo(int x, int y) {
    if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || visited[x][y]) {
      return false;
    }
    return true;
  }

  private void buildTrie() {
    trie = new Trie(new TrieNode());
    for (String word : dict) {
      trie.addWord(word);
    }
  }
}