百度的一道二面算法题分析：补全括号序列

title: 算法：括号序列补全
tags:PHP,算法,面试
grammar_cjkRuby: true
---

算法题：补全括号序列

百度二面遇到的一个问题

大概意思就是

给出一个中括号序列，在序列前后可以加中括号字符，补全它。。。

当时没想起来解决办法，然后凉凉了，后来专门去搞了这道题，终于搞定

思路在注释里写的比较详细了，此处不再赘述（用了类似栈的思想）

<?php /** * 字符串转数组 * @param$str string 输入的字符串 * @return array 转换之后的结果数组 */ function strToArray($str) { // 强制转换为字符串 $str = (string)$str; $arr = []; // 计算长度，考虑中文 $len = mb_strlen($str); // 循环截取，放到数组中 for ($i = 0; $i < $len; ++$i) { $arr[] = mb_substr($str, $i, 1); } return $arr; } /** * 判断括号是否已匹配 * @param$str string 输入的括号序列 * @return array 返回结果[bool,简化之后的括号数组] */ function bracketsTest($str) { $ls = strToArray($str); $sp = 0; // StackPointer 把数组想象成一个栈，只在栈尾操作 if (strlen($str) == 0) { return [true, []]; } else if (strlen($str) == 1) { return [false, $ls]; } while ($sp + 1 < count($ls)) { // 如果栈尾的字符和下一个入栈字符匹配 if ($ls[$sp] == '[' && $ls[$sp + 1] == ']') { // 删除这两个字符 array_splice($ls, $sp, 2); if ($sp > 0) { // 栈尾指针前移1位 --$sp; } } else { // 入栈 ++$sp; } } if (count($ls) == 0) { return [true, []]; } else { echo implode($ls), "\n"; return [false, $ls]; } } /** * 补全括号序列 * @param$str string 待补全的括号序列 * @return string */ function completingBrackets($str) { // 先判断，得到判断结果和简化结果 $testRes = bracketsTest($str); if ($testRes[0]) { return $str; } // 左右需补全的字符串 $lC = $rC = ''; foreach ($testRes[1] as $b) { if ($b == '[') { $rC .= ']'; } else { $lC .= '['; } } // 拼合 return $lC . $str . $rC; } echo completingBrackets('][][');