每日一题——整数反转

题目描述

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例

#1
输入: "()"
输出: true

#2
输入: "()[]{}"
输出: true

#3
输入: "(]"
输出: false

#4
输入: "([)]"
输出: false

#5
输入: "{[]}"
输出: true

思路

• 初始化栈 S。
• 一次处理表达式的每个括号。
• 如果遇到开括号，我们只需将其推到栈上即可。这意味着我们将稍后处理它，让我们简单地转到前面的 子表达式。
• 如果我们遇到一个闭括号，那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号，那么我们将它从栈中弹出并继续处理。否则，这意味着表达式无效。
• 如果到最后我们剩下的栈中仍然有元素，那么这意味着表达式无效。

代码

PHP

/**
 * @param String $s
 * @return Boolean
 */
# 方法一
function isValid($s) {
    $map = [
        ")" => "(",
        "}" => "{",
        "]" => "[",
    ];

    $len = strlen($s);
    if ($len == 0)
        return true;
    
    // 奇数个字符，必然不符合
    if ($len % 2 == 1) {
        return false;
    }

    $stack = [];
    //s中出现map的key则弹出，没有出现则入栈
    for ($i = 0; $i < $len; $i++) {
        if (isset($map[$s[$i]])) {
            if(end($stack) == $map[$s[$i]]) {
                array_pop($stack);	// 这里使用 array_unshift 和 array_shift 性能要比 array_push 和 array_pop 要低
            } else {
                return false;
            }
        } else {
            array_push($stack, $s[$i]);
        }
    }

    if (count($stack) > 0) {
        return false;
    }

    return true;
}

# 方法二
function isValid($s) {
    $map = [
        ")" => "(",
        "}" => "{",
        "]" => "[",
    ];

    $len = strlen($s);
    if ($len == 0)
        return true;

    // 奇数个字符，必然不符合
    if ($len % 2 == 1) {
        return false;
    }

    $stack = new SplStack();	// SplStack：通过使用一个双向链表来提供栈的主要功能
    for ($i =0; $i<$len; $i++) {
        if (isset($map[$s[$i]])) {
            if (!$stack->isEmpty()  && $stack->top() == $map[$s[$i]]) {
                $stack->pop();
            } else {
                return false;
            }
        } else {
            $stack->push($s[$i]);
        }
    }

    if (count($stack) > 0) {
        return false;
    }

    return true;
}

Golang

func isValid(s string) bool {
    if s == "" {
		return true
	}

	var stack []uint8

	m := map[uint8]uint8{
		'}': '{',
		')': '(',
		']': '[',
	}

    for i := 0; i < len(s); i++ {
		if s[i] == '{' || s[i] == '[' || s[i] == '(' {
			stack = append(stack, s[i])
		} else {
			if len(stack) == 0 {
				return false
			}
			
			if m[s[i]] != stack[len(stack)-1] {
				return false
			}
			
			stack = stack[:len(stack)-1]
		}
	}
	
	return len(stack) == 0
}