string match
收到面試的題目是要寫字串匹配~
題目限制使用 for 迴圈（模擬出 indexOf 的方法），以最少迴圈及比對資源，完成最快及有效率的運算，從長字串中，找出短字串出現的位置。
總之先來寫看看！
首先的想法就是遍歷所有長字串，比對跟短字串的第一個符號是否相同，相同就繼續往下比。
但！三秒之後就知道這樣比對次數太多了！❌
...
既然我們會知道長字串跟短字串是甚麼，且不需要考慮尾巴循環到頭的情境：
比如
長字串是 `aa.123.bb`
短字串是 `bbaa`
這樣放到 function 裡應該是找不到，而不是找到 7
所以最多只需要比對到位置 4 就好，最後一個比對就是 `3.bb` 是否等於 `bbaa`
有思考方向了！先來寫個！
const longStr = "aa. 123 .bb"
const shortStr = "a. 123"
function findLocation(longString, shortString) {
const targetLen = shortString.length
const longArr = longString.split("")
const shortArr = shortString.split("")
// 因為不是一圈字串，所以不用判斷每個長字串的字元，只要判斷到 長-短
for (let characLocation = 0; characLocation < longStr.length - targetLen; characLocation++) {
console.log(`這是第 ${characLocation} 次迴圈`)
const compareArr = longArr.slice(characLocation, characLocation + targetLen)
console.log("compareArr", compareArr)
console.log("shortArrrr", shortArr)
if (compareArr === shortArr) {
return characLocation
}
}
}
findLocation(longStr, shortStr)這邊可以看到印出來的 log 長這樣，第二次迴圈就找到東西了
這是第 1 次迴圈
compareArr [ 'a', 'a', '.', ' ', '1', '2' ]
shortArrrr [ 'a', '.', ' ', '1', '2', '3' ]
這是第 2 次迴圈
compareArr [ 'a', '.', ' ', '1', '2', '3' ]
shortArrrr [ 'a', '.', ' ', '1', '2', '3' ]
這是第 3 次迴圈
compareArr [ '.', ' ', '1', '2', '3', ' ' ]
shortArrrr [ 'a', '.', ' ', '1', '2', '3' ]
這是第 4 次迴圈
compareArr [ ' ', '1', '2', '3', ' ', '.' ]
shortArrrr [ 'a', '.', ' ', '1', '2', '3' ]
這是第 5 次迴圈
compareArr [ '1', '2', '3', ' ', '.', 'b' ]
shortArrrr [ 'a', '.', ' ', '1', '2', '3' ]但是！為什麼沒有 return 呢？
因為我在前面把字串轉成陣列，而在 JS 中 == 跟 === 運算子在比較物件（包括陣列）時，會比較它們的引用（記憶體位置），而不是內容。
所以我應該轉比較的方法~
用
join()轉回字串這是最簡單直接的方法。將陣列元素連接成字串後進行比較。
優點是簡單高效,缺點是需要先將字串轉成陣列。
用
JSON.stringify()轉字串這種方法可以將陣列完整轉換成字串進行比較。
優點是能完整比較陣列內容,缺點是轉換成字串後比較起來可能不太直觀。
用 ES6 的
every()方法every()方法可以檢查陣列中每個元素是否滿足指定條件。這種方法可以寫一個自定義的比較函數,來完整比較兩個陣列的內容。
優點是更加靈活,缺點是需要額外的函數定義。
自己寫比較函式
這是最靈活的方式,可以根據具體需求自訂比較邏輯。
優點是可以完全控制比較過程,缺點是需要編寫額外的函數。
既然題目希望用最少的比對資源，所以用 every 跟自己寫比較函式都會再增加比對資源，所以我們選最簡單的 join()。另外別忘了要模仿 indexOf，所以找不到的話要返回 -1。
const longStr = "aa. 123 .bb"
const shortStr = "a. 123"
function findLocation(longString, shortString) {
const targetLen = shortString.length
const longArr = longString.split("")
const shortArr = shortString.split("")
// 因為不是一圈字串，所以不用判斷每個長字串的字元，只要判斷到 長-短
for (let characLocation = 0; characLocation < longStr.length - targetLen; characLocation++) {
// 長陣列分割出要被比較的陣列長度
const compareArr = longArr.slice(characLocation, characLocation + targetLen)
// 因為陣列比較會是比較記憶體位置而非內容，因此轉字串比較
if (compareArr.join("") === shortArr.join("")) {
return characLocation
}
}
return -1
}
console.log(findLocation(longStr, shortStr))印出來 1，用 indexOf() 驗證一下也是 1，大功告成！
...
但 ❗❗❗❗
為甚麼要轉陣列又轉回來呢？直接用 substring() 切字串也是一樣的
function findLocation(longString, shortString) {
const targetLen = shortString.length
// 因為不是一圈字串，所以不用判斷每個長字串的字元，只要判斷到 長-短
for (let characLocation = 0; characLocation < longString.length - targetLen; characLocation++) {
// 長字串分割出要被比較的字串長度
const compareArr = longString.substring(characLocation, characLocation + targetLen)
if (compareArr === shortString) {
return characLocation
}
}
return -1
}
console.log(findLocation(longStr, shortStr))這樣更簡單啦～
5433! 下次見!
Last updated