20. Valid Parentheses

//
//  main.swift
//  20. Valid Parentheses
//
//  Created by FlyingPuPu on 13/02/2017.
//  Copyright (c) 2017 FPP. All rights reserved.
//

/*
20. Valid Parentheses
Given a string containing just the characters
 '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and
 "()[]{}" are all valid but "(]" and "([)]" are not.

 Thinking:
 3个栈，为左符号，则入栈， 为右符号，如果栈最后一位为左符号，栈空，直接返回false
 ( { [   //左符号
 LeftSign  RightSign

//Error1: 理解错了意思，"([)]" 是不匹配的，应该要满足每次pop后只有左符号，只需要一个栈即可
*/

import Foundation

func isValid(_ s: String) -> Bool {
    let length = s.lengthOfBytes(using: .ascii)
    guard length > 0 else {
        return true
    }

    let leftSign: [Character] = ["(","{", "["]
    let rightSign: [Character] = [")", "}", "]"]
//    var characterStack:[[Character]] = Array<[Character]>(repeating: [], count: leftSign.count)
    var matchStack:[Character] = [Character]()

    //插入v, 匹配左右符号，并插入到对应的栈中，如果出现栈空，并为有符号的情况，直接返回false
    func push(_ v: Character) -> Bool {
        //匹配左符号，直接入栈
        if let leftIndex = leftSign.index(of: v) {
//            characterStack[leftIndex].append(v)
            matchStack.append(v)
        }

        //匹配右符号，栈空，直接返回 false，如果非空，栈 pop
        if let rightIndex = rightSign.index(of: v) {
            //栈非空，且栈顶是一个左符号的情况下，并且左右符号
            if let last = matchStack.last,
               let lastIndex = leftSign.index(of: last), rightIndex == lastIndex {
                matchStack.removeLast()
            }
            else {
                return false
            }
        }

        return true
    }

    for v in s.characters {
        if !push(v) {
            return false
        }
    }

    return matchStack.isEmpty
}

print(isValid(""))
print(isValid("("))
print(isValid("()(){}[]"))
print(isValid("([])"))