面试手撕代码必看！Python优雅栈 vs Shell魔幻替换，同一问题的两种编程哲学
面试手撕代码必看！Python优雅栈 vs Shell魔幻替换，同一问题的两种编程哲学
题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
1. 左括号必须用相同类型的右括号闭合。2. 左括号必须以正确的顺序闭合。3. 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：
s ="()"
输出：true示例 2：
输入：
s ="(]"
输出：false示例 3：
输入：
s ="(]"
输出：false示例 4：
输入：
s ="([])"
输出：true提示：
• 1 <= s.length <= 10000• s 仅由括号 '()[]{}' 组成
python代码
import sys
def isValid(s):
"""
:type s: str
:return type: bool
"""
stack = []
para_map = {')':'(', ']':'[', '}':'{'}
for c in s:
if c not in para_map:
stack.append(c)
elif not stack or stack.pop() != para_map.get(c):
return False
return not stack
if __name__ == '__main__':
print(isValid( sys.argv[1] )一、核心逻辑解析
1. 数据结构设计
•栈结构：用列表stack模拟栈，存储未匹配的左括号。•字典映射：para_map定义了右括号到左括号的映射关系（如')':'('），用于快速匹配闭合括号。
2. 遍历逻辑
for c in s:
if c not in para_map: # 当前字符是左括号
stack.append(c)
else: # 当前字符是右括号
if not stack or stack.pop() != para_map.get(c):
return False•左括号处理：直接压入栈（如'('、'['、'{'）。•右括号匹配：检查栈顶是否为其对应的左括号，若匹配则弹出栈顶元素，否则返回False。
3. 最终校验
return not stack•遍历结束后，若栈为空，则说明所有括号均正确闭合，返回True。
二、关键语法与技巧
1.条件判断：if c not in para_map通过字典键快速判断字符是否为左括号。2.栈操作：stack.pop()直接弹出栈顶元素，与字典查询结合实现高效匹配。3.主程序入口：if __name__ == '__main__'表示直接执行脚本时调用isValid函数，并通过命令行参数sys.argv[1]获取输入。
三、测试用例示例
输入 | 输出 | 说明 |
|---|---|---|
"()" | True | 简单闭合 |
"()[]{}" | True | 多类型括号顺序闭合 |
"(]" | False | 类型不匹配 |
"([)]" | False | 错误嵌套顺序 |
"(" | False | 纯左括号，没有闭合 |
"}]" | False | 纯右括号，没有闭合 |
四、扩展思考
1.时间复杂度：由于单次遍历字符串，时间复杂度为 *O(n)*，空间复杂度最坏情况为 *O(n)*（如全左括号）。2.边界条件：需处理空字符串、纯左括号、纯右括号等情况。3.调试技巧：可通过插入print(stack)观察栈变化，或使用PyCharm的调试工具逐行分析。
如果需要进一步验证代码，可以尝试输入不同括号组合（如"{([])}"），观察输出是否符合预期。
shell代码
循环替换字符串的暴力解法，哈哈
#!/bin/bash
is_valid() {
local str="$1"
local prev=""
# 循环替换直到字符串不再变化
while [[ "$str" != "$prev" ]]; do
prev="$str"
# 替换所有成对括号
str=$(echo "$str" | sed 's/()//g; s/\[\]//g; s/{}//g')
done
# 判断最终字符串是否为空
[[ -z "$str" ]] && echo "true" || echo "false"
}
is_valid "$1"朋友们也可以动手试试
腾讯云开发者
