在解這題的過程中，發現了一些 test case 能提早判斷 return 掉，跑測試後能把時間壓在 100ms 以內，其他人分享的解法大都落在 300ms 上下，所以分享一下這個能穩定 beat 99% 其他人的優化方式。
解法
原題連結
這題主要是在 mxn 的矩陣中，透過走格子方式看是否能組出題目要求的字串 (word)，然後回傳 true or fasle。
大致上思路是先遍歷矩陣每個位置的字母，若找到跟 word 第一個字母一樣時就開始查找，從當前位置上下左右查找下一個字母，直到無法匹配或是匹配到最後一個字母。
並且我們需要紀錄已經找到的位置，這樣每次上下左右移動時才不會走回頭路。
var exist = function(board, word) {
const M = board.length
const N = board[0].length
var helper = function(m, n, i) {
if (word.length === i) return true // end of search
if (m >= M || n >= N || m < 0 || n < 0) return false // out of bondary
if (board[m][n] !== word[i]) return false // is not the correct route
const visitedChar = board[m][n]
board[m][n] = '.'
i++
// go up, down, left, right and change visited char to '.'
const result = helper(m+1, n, i) || helper(m-1, n, i) || helper(m, n+1, i) || helper(m, n-1, i)
board[m][n] = visitedChar
return result
}
for (let j = 0; j < M; j++) {
for (let k = 0; k < N; k++) {
if (helper(j, k, 0)) {
return true
}
}
}
return false
};
我們把上述程式碼拆成兩個部分。第一個部分就如同上段所述，先查找矩陣每個位置並執行 helper 查找，如果有匹配到第一個字母就繼續往上下左右執行 helper。
第二部分是 helper 函式需要處理邊際案例，例如當下個要查找的位置超出矩陣範圍時，就直接回傳 false。已經沒有需要匹配的字母時，也直接回傳 false。
這裡比較特別的是，helper 函式在每次要往上下左右執行下去前要先把當前位置的字母設為 . 來記錄已經匹配過的位置，之後在執行完成前再把該位置的字母還原回來。
到這裡其實就是標準解法了，在 Leetcode 上的 Solution 幾乎都是分享這種解法，且時間都是在 300ms 上下。
優化
其實在跑測試案例時，我有發現到一些邊際情況，例如：
const board = [
["A","A","A","A","A","A"],
["A","A","A","A","A","A"],
["A","A","A","A","A","A"],
["A","A","A","A","A","A"],
["A","A","A","A","A","A"],
["A","A","A","A","A","A"]
]
const word = "AAAAAAAAAAAAAAB"
這裡不用往上下左右匹配，一眼看就知道整個 board 少了 B 根本不可能匹配完 word。
所以優化的方向很明顯，在遍歷匹配前先計算 board 和 word 所需的字母數，接著比對看 board 有沒有缺少。
var exist = function(board, word) {
const M = board.length
const N = board[0].length
const boardMap = {}
const wordMap = {}
for (let j = 0; j < M; j++) {
for (let k = 0; k < N; k++) {
if (boardMap[board[j][k]]) {
boardMap[board[j][k]] ++
} else {
boardMap[board[j][k]] = 1
}
}
}
for (let j = 0; j < word.length; j++) {
if (wordMap[word[j]]) {
wordMap[word[j]] ++
} else {
wordMap[word[j]] = 1
}
}
for (let char in wordMap) {
if (!boardMap[char] || boardMap[char] < wordMap[char]) return false
}
}
雖然會多佔用一點點記憶體，但是平均的耗時可以減少到 100ms 以下。
這個解法只能優化平均耗時，最差的情況依舊是 O(M * N * 4^len)。
完整優化解法
var exist = function(board, word) {
const M = board.length
const N = board[0].length
/**
* Improve time complexity
* check letters in board could satisfied the word
*/
const boardMap = {}
const wordMap = {}
for (let j = 0; j < M; j++) {
for (let k = 0; k < N; k++) {
if (boardMap[board[j][k]]) {
boardMap[board[j][k]] ++
} else {
boardMap[board[j][k]] = 1
}
}
}
for (let j = 0; j < word.length; j++) {
if (wordMap[word[j]]) {
wordMap[word[j]] ++
} else {
wordMap[word[j]] = 1
}
}
for (let char in wordMap) {
if (!boardMap[char] || boardMap[char] < wordMap[char]) return false
}
var helper = function(m, n, i) {
if (word.length === i) return true // end of search
if (m >= M || n >= N || m < 0 || n < 0) return false // out of bondary
if (board[m][n] !== word[i]) return false // is not the correct route
const visitedChar = board[m][n]
board[m][n] = '.'
i++
// go up, down, left, right and change visited char to '.'
const result = helper(m+1, n, i) || helper(m-1, n, i) || helper(m, n+1, i) || helper(m, n-1, i)
board[m][n] = visitedChar
return result
}
for (let j = 0; j < M; j++) {
for (let k = 0; k < N; k++) {
if (helper(j, k, 0)) {
return true
}
}
}
return false
};
結語
每次解完 Leetcode 都會去看其他人用的解法和有沒有可以學習的地方，但這次看到幾個解法的耗時大都落在 300ms 上下，自己的都在 100ms 以內，比較下差異後特別寫了篇分享，另外我有也提供 Solution 在上面，希望有看到的朋友們可以幫我 Upvote 一下。