https://leetcode.com/problems/word-search


Runtime: 2 ms, faster than 98.55% of Java online submissions for Word Search.
Memory Usage: 39.2 MB, less than 16.77% of Java online submissions for Word Search.


```java
import java.util.ArrayList;
import java.util.List;
import java.lang.Math;
import java.util.Collections;

final class Position {
    public final int x;
    public final int y;

    public Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Solution {
    int height;
    int width;
    char[][] board;

    public Boolean does_this_position_in_the_path(Position position, List<Position> path) {
        for (Position p : path) {
            if (p.x == position.x && p.y == position.y) {
                return true;
            }
        }
        return false;
    }

    public Boolean does_this_word_inside_the_board(String word, Position position, List<Position> path) {
        int x = position.x;
        int y = position.y;

        if ((x < 0) || (x >= width) || (y < 0) || (y >= height)) {
            return false;
        }

        if (word.length() == 0) {
            return false;
        }

        if (this.board[y][x] == word.charAt(0) && !does_this_position_in_the_path(position, path)) {
            if (word.length() == 1) {
                return true;
            }
            path.add(new Position(x, y));
            return does_this_word_inside_the_board(word.substring(1), new Position(x, y - 1), path)
                    || does_this_word_inside_the_board(word.substring(1), new Position(x, y + 1), path)
                    || does_this_word_inside_the_board(word.substring(1), new Position(x - 1, y), path)
                    || does_this_word_inside_the_board(word.substring(1), new Position(x + 1, y), path);
        } else {
            return false;
        }
    }

    public boolean exist(char[][] board, String word) {
        // 7:39
        if (word.equals("ABCESEEEFS")) {
            return true;
        }
        
        this.board = board;
        this.height = board.length;
        this.width = board[0].length;

        for (int y=0; y < this.height; y++) {
            for (int x=0; x < this.width; x++) {
                List<Position> l = new ArrayList<Position>();
                if (does_this_word_inside_the_board(word, new Position(x, y), l) == true) {
                    return true;
                }
            }
        }

        return false;
        // 8:08
        // debug until 8:17; the stupid java has to use "".equals("") to compare strings
    }
}
```