求解Codewars有效括号验证Python解法的运行原理

核心思路 #

合法的纯括号组合必然存在至少一组相邻的匹配括号对，反复消除所有相邻匹配对后，合法字符串最终会被完全清空，存在不匹配括号或其他字符的字符串则无法被清空。

逐行代码解析 #

def validBraces(s):
    while '{}' in s or '()' in s or '[]' in s:
        s = s.replace('{}','')
        s = s.replace('[]','')
        s = s.replace('()','')
    return s == ""

• 第1行：定义函数validBraces，接收待验证的字符串s作为入参
• 第2行：循环判断条件：只要当前字符串中存在{}、()、[]任意一种相邻匹配括号对，就继续执行循环逻辑
• 第3~5行：全局替换所有相邻匹配括号对为空字符串，相当于把已经完成配对的括号直接从字符串中消除
• 第6行：循环结束后判断最终字符串是否为空，为空则所有括号全部匹配合法，返回True，否则返回False

示例运行过程 #

输入为"{[]}"的合法场景 #

初始s = "{[]}"
第一次进入循环：检测到存在相邻匹配对[]，替换后s变为{}
第二次进入循环：检测到存在相邻匹配对{}，替换后s变为空字符串
循环结束，判断空字符串等于空，返回True

输入为"{ab}"的非法场景 #

初始s = "{ab}"
循环条件检测：大括号中间夹了ab，不存在任何相邻匹配括号对，循环不执行
直接判断"{ab}" == ""，结果为False

补充说明 #

• str.replace()方法会替换字符串中所有完整匹配的子串，不会拆分匹配单个字符，符合消除完整配对括号的需求
• 如果字符串中存在括号以外的其他字符，这些字符永远不会被替换，最终字符串不可能为空，会直接判定为不合法，符合算法题的校验规则

内容的提问来源于stack exchange，提问作者AnubisTyrant