題目連結: https://leetcode.com/problems/longest-valid-parentheses/

Test cases:
Input: “” output: 0
Input: “(” output: 0
Input: “(()” output: 2
Input: “(())” output: 4
Input: “())()()” output: 4
Input: “()((()()” output: 4

解法參考:

https://leetcode.com/problems/longest-valid-parentheses/discuss/1349298/Swift%3A-Longest-Valid-Parentheses-(%2B-Test-Cases)

https://zxi.mytechroad.com/blog/stack/leetcode-32-longest-valid-parentheses/

法ㄧ:

    func longestValidParentheses(_ s: String) -> Int {
    	var result = 0
    	var start = 0
    	var stack: [Int] = []
    	for (index, c) in s.enumerated() {
    		if c == "(" {
    			stack.append(index)
    		} else {
    			if stack.isEmpty {
    			    start = index + 1
    			} else {
     				stack.removeLast()
                    if let last = stack.last {
                        result = max(result, index - last)
                    } else {
                        result = max(result, index - start + 1)
                    }
    			}
    		}
    	}
    	return result
    }

//自己練習的解法 （p.s. 最後一個case失敗，因為這個解法無法判斷由"("產生的間隔 ）
    func longestValidParentheses(_ s: String) -> Int {
        var result: [Int] = []
        var tmpResult = 0
        var stack: [Character] = []
        for c in s {
        	if c == "(" { 
        		stack.append(c)
        	} else {
        		if let last = stack.last {
        			stack.removeLast()
        			tmpResult += 2
        		} else {
        		    result.append(tmpResult)
        			tmpResult = 0
        			stack.removeAll()
        		}
        	}
        }

        if tmpResult != 0 {
            result.append(tmpResult)
        }
        return result.max() ?? 0
    }