package leetcode;

import java.util.List;

/**
 * https://leetcode.com/problems/word-search-ii/
 */
public class Problem212 {
    public List<String> findWords(char[][] board, String[] words) {
        // TODO
        return null;
    }

    public static void main(String[] args) {
        Problem212 prob = new Problem212();
        System.out.println(prob.findWords(new char[][]{
            {'o', 'a', 'a', 'n'},
            {'e', 't', 'a', 'e'},
            {'i', 'h', 'k', 'r'},
            {'i', 'f', 'l', 'v'}
        }, new String[]{"oath", "pea", "eat", "rain"})); // ["eat","oath"]
    }
}

@@ -29,19 +29,95 @@
 va.util.
-Lis
+ArrayList;%0Aimport java.util.HashSet;%0Aimport java.util.List;%0Aimport java.util.Se
 t;%0A%0A/**%0A
@@ -275,165 +275,1001 @@
     
-// TODO%0A        return null;%0A
+List%3CString%3E answer = new ArrayList%3C%3E();%0A        Set%3CString%3E set = new HashSet%3C%3E();%0A        for (String word : words) %7B%0A            set.add(word);%0A  
     
+  
 %7D
-%0A
 %0A    
-public static void main(String%5B%5D args) %7B%0A        Problem212 prob = new Problem212();%0A        System.out.println(prob.
+    int maxRow = board.length;%0A        int maxCol = board.length %3E 0 ? board%5B0%5D.length : 0;%0A        outer:%0A        for (int i = 0; i %3C maxRow; i++) %7B%0A            for (int j = 0; j %3C maxCol; j++) %7B%0A                boolean%5B%5D%5B%5D visited = new boolean%5BmaxRow%5D%5BmaxCol%5D;%0A                List%3CString%3E tmp = new ArrayList%3C%3E();%0A                for (String word : set) %7B%0A                    if (findWords(board, word, maxRow, maxCol, i, j, 0, visited)) %7B%0A                        tmp.add(word);%0A                        answer.add(word);%0A                    %7D%0A                %7D%0A                for (String word : tmp) %7B%0A                    set.remove(word);%0A                %7D%0A                if (set.isEmpty()) %7B%0A                    break outer;%0A                %7D%0A            %7D%0A        %7D%0A        return answer;%0A    %7D%0A%0A    private static boolean 
 find
@@ -1278,20 +1278,16 @@
 rds(
-new 
 char%5B%5D%5B%5D
 %7B%0A  
@@ -1286,219 +1286,953 @@
 %5B%5D%5B%5D
-%7B%0A            %7B'o', 'a', 'a', 'n'%7D,%0A            %7B'e', 't', 'a', 'e'%7D,%0A            %7B'i', 'h', 'k', 'r'%7D,%0A            %7B'i', 'f', 'l', 'v'%7D%0A        %7D, new String%5B%5D%7B%22oath%22, %22pea%22, %22eat%22, %22rain%22%7D)); // %5B%22eat%22,%22oath%22%5D
+ board, String word, int maxRow, int maxCol,%0A                                     int row, int col, int idx, boolean%5B%5D%5B%5D visited) %7B%0A        if (idx == word.length()) %7B%0A            return true;%0A        %7D%0A        if (row %3C 0 %7C%7C row == maxRow %7C%7C col %3C 0 %7C%7C col == maxCol) %7B%0A            return false;%0A        %7D%0A        if (visited%5Brow%5D%5Bcol%5D) %7B%0A            return false;%0A        %7D%0A        if (board%5Brow%5D%5Bcol%5D != word.charAt(idx)) %7B%0A            return false;%0A        %7D%0A        visited%5Brow%5D%5Bcol%5D = true;%0A        boolean a = findWords(board, word, maxRow, maxCol, row - 1, col, idx + 1, visited);%0A        boolean b = findWords(board, word, maxRow, maxCol, row, col + 1, idx + 1, visited);%0A        boolean c = findWords(board, word, maxRow, maxCol, row + 1, col, idx + 1, visited);%0A        boolean d = findWords(board, word, maxRow, maxCol, row, col - 1, idx + 1, visited);%0A        visited%5Brow%5D%5Bcol%5D = false; // backtracking%0A        return a %7C b %7C c %7C d;
 %0A   

Solve problem 212