我最近遇到的一個練習讓我有點困惑。
這似乎是一項簡單的任務，我已經提出了我的解決方案，但結果證明它沒有通過所有測驗：D
在示例中，我找到了兩個示例子字串：
Input: S = "(()("
Output: 2
Explanation: The longest valid
substring is "()". Length = 2.
和
Input: S = "()(())("
Output: 6
Explanation: The longest valid
substring is "()(())". Length = 6.
乍一看，一切都很清楚。
我想出了我的解決方案：
class Solution {
findMaxLen(s) {
if (!s || !s.length) throw new Error('Invalid input value provided')
let openIndex = null
let closingIndex = null
for (let i = 0; i < s.length; i ) {
if (s[i] == '(' && !openIndex) openIndex = i 1
if (s[i] == ')') closingIndex = i 1
}
if(!closingIndex || !openIndex) throw new Error('Invalid substring')
return closingIndex - openIndex 1
}
}
所以，我的解決方案應該解決試圖The longest substring用左括號和右括號查找的問題。
但是它沒有通過輸入值的測驗：(((()
正確答案在哪里2，我的輸出是5
這與示例中提供的(((()不同()(())(嗎？
我想我不完全理解子字串是什么或什么的想法......
uj5u.com熱心網友回復：
這個偽代碼應該可以作業。一些錯誤或邊緣情況可能有松散的結局，因為我剛剛在這里即時寫了這篇文章。隨意測驗它并指出遺漏。
helper_stack = null
max_valid_len = 0
running_len = 0
for i=0 to input_s.length:
if helper_stack.length == 0:
if input_s[i] == ')':
running_len = 0
continue
else:
helper_stack.push('(')
else:
if input_s[i] == '(':
helper_stack.push('(')
else:
helper_stack.pop()
running_len = 2
if running_len > max_valid_len:
max_valid_len = running_len
編輯：解釋
根據您的邏輯，您沒有跟蹤opening and closing括號的順序，這很重要。如果 aclosing bracket在打開之前，字串默認變為無效。因此，在這里使用堆疊是有意義的。
如果我們在 open 之前遇到右括號，我們會從那個點重新開始。因此，我們設定了running_len = 0. 對于每次遇到右括號，如果有一個左括號來平衡它，我們只需將其彈出，因為它的一對（當我們考慮字串的長度時，running_len = 2是字符），就完成了。
只需稍加修改，我們甚至可以max_valid_substring根據需要進行復制。然而，在我們的例子中，我們甚至可以只使用一個整數而不是helper_stack。對于每個push('(')操作，只需執行var = 1和var -= 1for pop，這也應該可以解決問題。請注意，在這里，我們沒有明確使用stack，但這仍然是概念上的LIFO = last in first out，基本上是堆疊。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/391633.html
標籤：javascript 算法 子串
下一篇：計算字串中子字串的重疊出現次數