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

wxjblog 2018-04-22 原文

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('][][');