cpp 解法, 执行用时: 176 ms, 内存消耗: 59.6 MB, 提交时间: 2023-09-14 01:10:47

class Solution {
public:
    string word;
    
    bool check(string & s) {
        int n = (int)s.size();
        for (int i = 0; i < n; i ++) {
            if (s[i] == ' ')
                continue;
            else
                if (s[i] != word[i])
                    return false;
        }
        return true;
    }


    bool placeWordInCrossword(vector<vector<char>>& board, string word) {
        this->word = word;
        int Row = (int)board.size();
        int Col = (int)board[0].size();

        int wn = (int)word.size();

        //--------先按行
        for (int r = 0; r < Row; r ++) {
            int c = 0;
            while (c < Col) {
                if (board[r][c] == '#') {
                    c ++;
                } else {
                    string s = "";
                    int cur = 0;
                    while (c < Col && board[r][c] != '#')
                    {
                        s.push_back(board[r][c]);
                        cur ++;
                        c ++;
                    }
                    if (cur == wn)
                    {
                        string tmp = s;    reverse(tmp.begin(), tmp.end());
                        if (check(s) == true || check(tmp) == true)
                            return true;
                    }
                }
            }
            c ++;
        }

        //--------再按列
        for (int c = 0; c < Col; c ++)
        {
            int r = 0;
            while (r < Row)
            {
                if (board[r][c] == '#')
                {
                    r ++;
                }
                else
                {
                    string s = "";
                    int cur = 0;
                    while (r < Row && board[r][c] != '#')
                    {
                        s.push_back(board[r][c]);
                        cur ++;
                        r ++;
                    }
                    if (cur == wn)
                    {
                        string tmp = s;    reverse(tmp.begin(), tmp.end());
                        if (check(s) == true || check(tmp) == true)
                            return true;
                    }
                    r ++;
                }
            }
        }

        return false;
    }
};

python3 解法, 执行用时: 144 ms, 内存消耗: 51.4 MB, 提交时间: 2023-09-14 01:09:48

class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        def check(s: str) -> bool:
            for i in range(wn):
                if s[i] == ' ':
                    continue
                else:
                    if s[i] != word[i]:
                        return False
            return True
        
        
        Row = len(board)
        Col = len(board[0])
        
        wn = len(word)

        #--------先按行
        for r in range(Row):
            c = 0
            while c < Col:
                if board[r][c] == '#':
                    c += 1
                elif board[r][c].isalpha() or board[r][c] == ' ':
                    s = ''
                    cur = 0
                    while c < Col and (board[r][c].isalpha() or board[r][c] == ' '):
                        s += board[r][c]
                        cur += 1
                        c += 1
                    if cur == wn:
                        if check(s) == True or check(s[::-1]):
                            return True
                    c += 1
        #--------再按列
        for c in range(Col):
            r = 0
            while r < Row:
                if board[r][c] == '#':
                    r += 1
                elif board[r][c].isalpha() or board[r][c] == ' ':
                    s = ''
                    cur = 0
                    while r < Row and (board[r][c].isalpha() or board[r][c] == ' '):
                        s += board[r][c]
                        cur += 1
                        r += 1
                    if cur == wn:
                        if check(s) == True or check(s[::-1]) == True:
                            return True
                    r += 1
                            
        return False

golang 解法, 执行用时: 16 ms, 内存消耗: 7.3 MB, 提交时间: 2023-09-14 01:09:09

func placeWordInCrossword(board [][]byte, word string) bool {
	m, n, k := len(board), len(board[0]), len(word)
	// 遍历行
	for _, row := range board {
		for j := 0; j < n; j++ {
			if row[j] == '#' {
				continue
			}
			// 遍历并匹配两个 # 之间的字符
			j0, ok1, ok2 := j, true, true
			for ; j < n && row[j] != '#'; j++ { // 注意这里的 j 就是外层循环的 j，因此整体复杂度是线性的
				if j-j0 >= k || row[j] != ' ' && row[j] != word[j-j0] { // 正序匹配 word
					ok1 = false
				}
				if j-j0 >= k || row[j] != ' ' && row[j] != word[k-1-j+j0] { // 倒序匹配 word
					ok2 = false
				}
			}
			if (ok1 || ok2) && j-j0 == k { // 只要正序和倒序中有一个匹配成功，且两个 # 之间的字符长度恰好为 word 的长度，就返回 true
				return true
			}
		}
	}

	// 遍历列（同上）
	for j := 0; j < n; j++ {
		for i := 0; i < m; i++ {
			if board[i][j] == '#' {
				continue
			}
			i0, ok1, ok2 := i, true, true
			for ; i < m && board[i][j] != '#'; i++ {
				if i-i0 >= k || board[i][j] != ' ' && board[i][j] != word[i-i0] {
					ok1 = false
				}
				if i-i0 >= k || board[i][j] != ' ' && board[i][j] != word[k-1-i+i0] {
					ok2 = false
				}
			}
			if (ok1 || ok2) && i-i0 == k {
				return true
			}
		}
	}
	return false
}