前言
在大學時期，我曾經看過這個問題，雖然看起來很簡單，但是我發現我沒有很好的解法，最後放棄了，可是我相信我未來有能力可以解決掉這題。
經過幾年後，我認為我的經驗與思維有所提升，應該可以再次挑戰這個問題，即使過程中遇到困難，我也相信可以想辦法解決掉。
題目
給一個字串 s 包含 ([{}]) 大中小括弧，確認輸入字串是否符合規則
需要左右括弧對應
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.
解題過程
原先爲這個封閉條件一定是兩兩一組，所以只需要確認偶數index與奇數index是否為對稱的
function isValid(s: string): boolean {
const right = [')', ']', '}'];const len = s.length;
let seq: number;
for(let i = 0 ; i < len ; i++) {
if(i % 2 === 0) {
seq = findLeftSeq(s[i]);
} else {
if(right[seq] !== s[i]) {
return false;
}
}
}
return true;};function findLeftSeq(char: string): number {
const left = ['(', '[', '{'];
return left.findIndex(x => x === char);
}
但這種做法少考量到 ([]) 這種情況
說實話這裡應該是我對題目(英文)理解有誤導致的
但我也暫時沒有更好的解法…
我突然回想起以前曾想過一個特別的方法，即將括號轉換為數字表示，然後對這些數字進行加減運算，最後比對運算結果是否小於 0。我認為這樣或許可以解決掉這個問題。
另外，我也考慮到中間隔太多較小數值的括號會累積成數值大的括號，所以刻意將數字隔開一點。
function isValid(s: string): boolean {// 避免太長
const mapValue = {
"{": 100000000,
"[": 10000,
"(": 1,
"}": -100000000,
"]": -10000,
")": -1
}; let processSum: number = 0; const len = s.length; for(let i = 0 ; i < len ; i++) {
const char = s[i];
processSum += mapValue[char];
if(processSum < 0) {
return false;
}
} return true;};
但這種方式好像也好像有點考量不足，沒有處理到類似這種情形 ([)] ，而且使用數字計算可能還會有其他問題，應該還是要回到最原始的字串比對就好了
function isValid(s: string): boolean {const processLst: string[] = [];
const left = ['(', '[', '{'];
const right = [')', ']', '}']; const len = s.length;
for(let i = 0 ; i < len ; i++) {
const char = s[i];
if(left.includes(char)) {
// 如果是左括弧，就放入處理列表
processLst.push(char);
} else {
// 右括弧
// 如果是右括弧，但處理列表為空，表示這個右括弧是多的(沒有封閉)
if(processLst.length === 0) {
return false;
} // 取得到處理列表的最後一個
const currentLast = processLst[processLst.length - 1];
const leftIdx = left.findIndex(x => x === currentLast);
// 檢查目前處理列表最後一個字元是否與當前字元對應
if(char !== right[leftIdx]) {
// 否: 表示未形成封閉
return false;
} else {
// 是: 將處理列表的最後一個元素剔除
processLst.splice(-1);
}
}
}
return true;};
// [
好像很完美了
但是卻少考慮到 [ 這種情況，如果今天多出來的是左括號，在上面的程式就會失敗…
function isValid(s: string): boolean {const processLst: string[] = [];
const left = ['(', '[', '{'];
const right = [')', ']', '}']; const len = s.length;
for(let i = 0 ; i < len ; i++) {
const char = s[i];
if(left.includes(char)) {
// 如果是左括弧，就放入處理列表
processLst.push(char);
} else {
// 右括弧
// 如果是右括弧，但處理列表為空，表示這個右括弧是多的(沒有封閉)
if(processLst.length === 0) {
return false;
} // 取得到處理列表的最後一個
const currentLast = processLst[processLst.length - 1];
const leftIdx = left.findIndex(x => x === currentLast);
// 檢查目前處理列表最後一個字元是否與當前字元對應
if(char !== right[leftIdx]) {
// 否: 表示未形成封閉
return false;
} else {
// 是: 將處理列表的最後一個元素剔除
processLst.splice(-1);
}
}
}
// 如果處理列表還有元素表示沒有形成對應
return processLst.length === 0;};
這樣一來就完成了!!!
結果
心得
在經歷第一次失敗後，我放置了這個問題十幾天。最近因為需要準備部門內的分享報告，暫時不想面對這個問題。我對這題沒有想法，所以一直擺著不理。
直到4月下旬迎來了一陣強烈的春雨，氣溫驟降，思緒也漸漸平靜下來，我覺得該是來解決這個問題了。在解題的過程中我回想起之前試過的方法，把括弧賦值進行運算，但發現事情沒那麼簡單。後來我轉變思路，直接比對字元並確認是否達到封閉，只要符合條件(達成封閉)就把這個括弧抵銷掉，順著這個思路，我終於解出問題。
希望自己能夠在以後的開發過程中想起這次的歷程，提醒自己遇到困難的問題解不了，即使有一些感覺很奇怪的方法，都應該去嘗試看看，即使是錯的，但我認為這也會成為成功得到解答的養分。這次的經驗讓我更加堅信，在解決問題的路上，每一次嘗試都有其價值，每一個錯誤都是一次寶貴的學習。
