You are given an m x n matrix board, representing the current state of a crossword puzzle. The crossword contains lowercase English letters (from solved words), ' ' to represent any empty cells, and '#' to represent any blocked cells.

A word can be placed horizontally (left to right or right to left) or vertically (top to bottom or bottom to top) in the board if:


	It does not occupy a cell containing the character '#'.
	The cell each letter is placed in must either be ' ' (empty) or match the letter already on the board.
	There must not be any empty cells ' ' or other lowercase letters directly left or right of the word if the word was placed horizontally.
	There must not be any empty cells ' ' or other lowercase letters directly above or below the word if the word was placed vertically.


Given a string word, return true if word can be placed in board, or false otherwise.

&nbsp;
Example 1:

Input: board = [["#", " ", "#"], [" ", " ", "#"], ["#", "c", " "]], word = "abc"
Output: true
Explanation: The word "abc" can be placed as shown above (top to bottom).


Example 2:

Input: board = [[" ", "#", "a"], [" ", "#", "c"], [" ", "#", "a"]], word = "ac"
Output: false
Explanation: It is impossible to place the word because there will always be a space/letter above or below it.

Example 3:

Input: board = [["#", " ", "#"], [" ", " ", "#"], ["#", " ", "c"]], word = "ca"
Output: true
Explanation: The word "ca" can be placed as shown above (right to left). 


&nbsp;
Constraints:


	m == board.length
	n == board[i].length
	1 &lt;= m * n &lt;= 2 * 105
	board[i][j] will be ' ', '#', or a lowercase English letter.
	1 &lt;= word.length &lt;= max(m, n)
	word will contain only lowercase English letters.


class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        W = len(word)
        
        def valid(x, y):
            return 0 <= x < m and 0 <= y < n
        
        def place(x, y, word, direction):
            dx, dy = direction
            for c in word:
                if not valid(x, y) or board[x][y] == '#' or (board[x][y] != ' ' and board[x][y] != c):
                    return False
                x, y = x+dx, y+dy
            return True
            
        
        for x in range(m):
            for y in range(n):
                if board[x][y] == '#' or (board[x][y] != ' ' and board[x][y] != word[0]):
                    continue
                
                # left to right
                if (not valid(x, y-1) or board[x][y-1] == '#') and (not valid(x, y+W) or board[x][y+W] == '#') and place(x, y, word, [0, 1]):
                    return True
                
                # right to left
                if (not valid(x, y+1) or board[x][y+1] == '#') and (not valid(x, y-W) or board[x][y-W] == '#') and place(x, y, word, [0, -1]):
                    return True
                
                # top to bottom
                if (not valid(x-1, y) or board[x-1][y] == '#') and (not valid(x+W, y) or board[x+W][y] == '#') and place(x, y, word, [1, 0]):
                    return True
                
				# bottom to top
                if (not valid(x+1, y) or board[x+1][y] == '#') and (not valid(x-W, y) or board[x-W][y] == '#') and place(x, y, word, [-1, 0]):
                    return True
                
        return False
class Solution {
    public boolean placeWordInCrossword(char[][] board, String word) {
        String curr = "";

        Trie trie = new Trie();

        // Insert all horizontal strings
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '#') {
                    insertIntoTrie(trie, curr);
                    curr = "";
                }
                else {
                    curr += board[i][j];
                }
            }
            insertIntoTrie(trie, curr);
            curr = "";
        }

        // Insert all vertical strings
        for (int i = 0; i < board[0].length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[j][i] == '#') {
                    insertIntoTrie(trie, curr);
                    curr = "";
                }
                else {
                    curr += board[j][i];
                }
            }
            insertIntoTrie(trie, curr);
            curr = "";
        }

        return trie.isPresent(word);
    }

    // Insert string and reverse of string into the trie
    private void insertIntoTrie(Trie trie, String s) {
        trie.insert(s);
        StringBuilder sb = new StringBuilder(s);
        sb.reverse();
        trie.insert(sb.toString());
    }

    class TrieNode {
        Map<Character, TrieNode> children;
        boolean isEnd;

        TrieNode() {
            children = new HashMap<>();
            isEnd = false;
        }

    }

    class Trie {
        TrieNode root;

        Trie() {
            root = new TrieNode();
        }

        void insert(String s) {
            TrieNode curr = root;

            for (int i = 0; i < s.length(); i++)
            {
                char c = s.charAt(i);
                if (!curr.children.containsKey(c)) {
                    curr.children.put(c, new TrieNode());
                }

                curr = curr.children.get(c);
            }

            curr.isEnd = true;
        }

        boolean isPresent(String key) {
            TrieNode curr = root;
            return helper(key, 0, root);

        }

        boolean helper(String key, int i, TrieNode curr) {
            if (curr == null)
                return false;

            if (i == key.length())
                return curr.isEnd;

            char c = key.charAt(i);
            return helper(key, i + 1, curr.children.get(c)) || helper(key, i + 1, curr.children.get(' '));

        }
    }
}
class Solution {
public:
    bool placeWordInCrossword(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; j < n; j++){
                if(board[i][j] != '#'){
                    if(valid(board, i-1, j) && check(board, word, i, j, 0, true, 1)) return true;
                    if(valid(board, i+1, j) && check(board, word, i, j, 0, true, -1)) return true;
                    if(valid(board, i, j-1) && check(board, word, i, j, 0, false, 1)) return true;
                    if(valid(board, i, j+1) && check(board, word, i, j, 0, false, -1)) return true;
                }
            }
        }
        return false;
    }

    bool check(vector<vector<char>>& board, string &word, int x, int y, int pos, bool vertical, int inc){
        if(pos == word.size()){
            if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size()) return true;
            return board[x][y] == '#';
        }
        if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size()) return false;
        if(board[x][y] == '#') return false;
        if(board[x][y] != ' ' && board[x][y] != word[pos]) return false;
        int newx = x + vertical * inc;
        int newy = y + (!vertical) * inc;
        return check(board, word, newx, newy, pos+1, vertical, inc);
    }

    bool valid(vector<vector<char>>& board, int x, int y){
        if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size()) return true;
        return board[x][y] == '#';
    }
};
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var placeWordInCrossword = function(board, word) {
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (i === 0 || board[i - 1][j] === '#') {
                if (match(getFill(i, j, false))) {
                    return true;
                }
            }
            if (j === 0 || board[i][j - 1] === '#') {
                if (match(getFill(i, j, true))) {
                    return true;
                }
            }
        }
    }
    return false;

    function getFill(x, y, goRight) {
        if (x >= 0 && x < board.length && y >= 0 && y < board[0].length && board[x][y] !== '#') {
            return goRight ? board[x][y] + getFill(x, y + 1, goRight) : board[x][y] + getFill(x + 1, y, goRight);
        }
        return '';
    }

    function match(str) {
        if (str.length !== word.length) {
            return false;
        }
        let fromLeft = true;
        let fromRight = true;
        let l = 0;
        let r = str.length - 1;
        for (let each of word) {
            if (!fromLeft && !fromRight) {
                return false;
            }
            if (fromLeft) {
                if (each !== str[l] && str[l] !== ' ') {
                    fromLeft = false;
                }
                l++;
            }
            if (fromRight) {
                if (each !== str[r] && str[r] !== ' ') {
                    fromRight = false;
                }
                r--;
            }
        }
        return fromLeft || fromRight;
    }
};
Check if Word Can Be Placed In Crossword