題目 簡(jiǎn)單

有效括號(hào)字符串為空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括號(hào)字符串，+ 代表字符串的連接。例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括號(hào)字符串。

如果有效字符串 S 非空，且不存在將其拆分為 S = A+B 的方法，我們稱(chēng)其為原語(yǔ)（primitive），其中 A 和 B 都是非空有效括號(hào)字符串。

給出一個(gè)非空有效字符串 S，考慮將其進(jìn)行原語(yǔ)化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括號(hào)字符串原語(yǔ)。

對(duì) S 進(jìn)行原語(yǔ)化分解，刪除分解中每個(gè)原語(yǔ)字符串的最外層括號(hào)，返回 S 。

示例 1：
輸入："(()())(())"
輸出："()()()"
解釋?zhuān)?br> 輸入字符串為 "(()())(())"，原語(yǔ)化分解得到 "(()())" + "(())"，
刪除每個(gè)部分中的最外層括號(hào)后得到 "()()" + "()" = "()()()"。

示例 2：
輸入："(()())(())(()(()))"
輸出："()()()()(())"
解釋?zhuān)?br> 輸入字符串為 "(()())(())(()(()))"，原語(yǔ)化分解得到 "(()())" + "(())" + "(()(()))"，
刪除每隔部分中的最外層括號(hào)后得到 "()()" + "()" + "()(())" = "()()()()(())"。

示例 3：
輸入："()()"
輸出：""
解釋?zhuān)?br> 輸入字符串為 "()()"，原語(yǔ)化分解得到 "()" + "()"，
刪除每個(gè)部分中的最外層括號(hào)后得到 "" + "" = ""。

解題思路

用一個(gè)整形標(biāo)記即可，左括號(hào)出現(xiàn) +1，如果值大于 1 表示為內(nèi)部左括號(hào)，拼接到返回字符串即可；如果右括號(hào)出現(xiàn)則 -1，如果此時(shí)的值大于 0 表示為內(nèi)部右括號(hào)，拼接到返回字符串即可。 時(shí)間復(fù)雜度: O(N)，N 為字符串的長(zhǎng)度。

CODE

/**
 * @param {string} S
 * @return {string}
 */
var removeOuterParentheses = function (S) {
  const sArray = S.split('');
  var tag = 0;
  var result = '';

  for (index = 0; index < sArray.length; index++) {
    if (sArray[index] === '(') {
      tag ++;
      if (tag > 1) {
        result += sArray[index];
      }
    } else {
      tag --;
      if (tag > 0) {
        result += sArray[index];
      }
    }
  }
  return result;
};

removeOuterParentheses("(()())(())")

這是在我看了leetCode上的解題思路然后寫(xiě)的，下面我記錄下我拿到題目后的自己的思路和解法。

用一個(gè)標(biāo)識(shí)符記錄原語(yǔ)的開(kāi)始索引，然后用一個(gè)數(shù)組記錄內(nèi)部左括號(hào)的索引，當(dāng)匹配到右括號(hào)就刪除數(shù)組中的一個(gè)左括號(hào)索引值（表示匹配了一對(duì)括號(hào)）.當(dāng)數(shù)組為空表示一個(gè)原語(yǔ)匹配完成，則記錄到結(jié)果中。
注意：我這個(gè)思路耗時(shí)和耗費(fèi)內(nèi)存較高，不推薦，只是記錄下我的思路??

/**
 * @param {string} S
 * @return {string}
 */
var removeOuterParentheses = function (S) {
  var sArray = S.split('');
  var primitiveStart = -1;
  var startList = [];
  var result = '';

  for (index = 0; index < sArray.length; index++) {
    if (sArray[index] === '(') {
      if (primitiveStart === -1) {
        primitiveStart = index; //記錄原語(yǔ)的開(kāi)始index
      } else {
        startList.push(index);
      }
    } else {
      let len = startList.length;
      let lastIndex = startList[len - 1];
      if (len <= 0) {
        var result = sArray.slice(primitiveStart, index + 1);
        result += result.slice(1, result.length - 1).join('');
        primitiveStart = -1;
      } else {
        startList.splice(len -1);
      }
    }
  }
  return result;
};