浜岀淮鐭╅樀鍗曡瘝鎼滅储锛欴FS鍥炴函绠楁硶娣卞害鍓栨瀽

涓€銆侀棶棰樻弿杩?/h2>

缁欏畾涓€涓簩缁村瓧绗︾煩闃靛拰鐩爣鍗曡瘝锛屽垽鏂兘鍚﹂€氳繃涓婁笅宸﹀彸鐩搁偦鐨勬牸瀛愭寜椤哄簭鎷煎嚭璇ュ崟璇嶃€傛瘡涓牸瀛愬湪涓€鏉¤矾寰勪腑鍙兘浣跨敤涓€娆°€?/p>

board = [
  ['C','O','D','E'],
  ['M','A','S','T'],
  ['E','R','X','Y']
]

word = "MASTER" 鈫?true  (鍙互鎵惧埌璺緞)
word = "CODE"   鈫?true
word = "CODER"  鈫?false (R涓嶄笌E鐩搁偦)

浜屻€佺畻娉曟€濊矾锛欴FS + 鍥炴函

1. 閬嶅巻鐭╅樀锛屾壘鍒颁笌鍗曡瘝棣栧瓧姣嶅尮閰嶇殑璧风偣
2. 浠庤捣鐐瑰嚭鍙戯紝DFS灏濊瘯鍥涗釜鏂瑰悜
3. 浣跨敤visited鏍囪閬垮厤閲嶅浣跨敤鏍煎瓙
4. 鍥炴函鏃跺彇娑堟爣璁帮紝灏濊瘯鍏朵粬璺緞

涓夈€佷唬鐮佸疄鐜?/h2>

function wordSearch(board: string[][], word: string): boolean {
    const rows = board.length;
    const cols = board[0].length;
    const visited: boolean[][] = Array.from(
        {length: rows}, () => Array(cols).fill(false)
    );
    
    // 鍥涗釜鏂瑰悜锛氫笂銆佷笅銆佸乏銆佸彸
    const directions = [[-1,0], [1,0], [0,-1], [0,1]];
    
    function dfs(row: number, col: number, index: number): boolean {
        // 鎴愬姛鍖归厤鎵€鏈夊瓧绗?
        if (index === word.length) return true;
        
        // 杈圭晫妫€鏌?
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            return false;
        }
        
        // 宸茶闂垨瀛楃涓嶅尮閰?
        if (visited[row][col] || board[row][col] !== word[index]) {
            return false;
        }
        
        // 鏍囪璁块棶
        visited[row][col] = true;
        
        // 灏濊瘯鍥涗釜鏂瑰悜
        for (const [dr, dc] of directions) {
            if (dfs(row + dr, col + dc, index + 1)) {
                return true;
            }
        }
        
        // 鍥炴函锛氬彇娑堟爣璁?
        visited[row][col] = false;
        return false;
    }
    
    // 浠庢瘡涓彲鑳界殑璧风偣寮€濮嬫悳绱?
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (dfs(i, j, 0)) return true;
        }
    }
    
    return false;
}

鈿狅笍 鍥炴函鍏抽敭锛?/strong>閫掑綊杩斿洖鍓嶅繀椤?code>visited[row][col] = false锛屽惁鍒欎細褰卞搷鍏朵粬璺緞鐨勬悳绱€?

鍥涖€佷紭鍖栨妧宸?/h2>

• 鍘熷湴鏍囪锛氱敤鐗规畩瀛楃(濡?#')涓存椂鏇挎崲锛岀渷鍘籿isited鏁扮粍
• 鍓灊锛氶妫€鏌ュ崟璇嶄腑姣忎釜瀛楁瘝鏄惁閮藉湪鐭╅樀涓嚭鐜?/li>
• 鍙嶅悜鎼滅储锛氳嫢鍗曡瘝鏈熬瀛楃鏇寸█灏戯紝鍙嶅悜鎼滅储鏁堢巼鏇撮珮

浜斻€佸鏉傚害鍒嗘瀽

• 鏃堕棿锛歄(m 脳 n 脳 4^L)锛孡涓哄崟璇嶉暱搴?/li>
• 绌洪棿锛歄(L)锛岄€掑綊鏍堟繁搴?/li>

鍏€佺浉鍏抽鐩?/h2>

1. 鍗曡瘝鎼滅储II锛圱rie鏍?DFS锛?/li>
2. 宀涘笨鏁伴噺锛堣繛閫氬尯鍩熻鏁帮級
3. 璺緞鎬诲拰锛堟爲鐨凞FS锛?/li>

DFS 鍥炴函绠楁硶 鐭╅樀鎼滅储 閫掑綊