帶有平衡括號的子串

以下問題在面試中被問到我的朋友：給定一個只包含'（'和'）'的字符串。找到平衡括號的子串總數注意：輸入字符串已經平衡。帶有平衡括號的子串

我能想到這個問題的唯一解決方案就是需要n^3次的蠻力。有沒有更快的解決方案possible.If有，那麼我也想知道建立這種方法。

2016-03-22 suraj

請發佈您到目前爲止的代碼。 – BPS

現在沒有做任何代碼我現在可以只是想到蠻力，這是每個子字符串檢查它有平衡的遺囑或不。檢查將花費O（長度）時間使用堆棧。我首先想到了算法，然後編寫代碼 – suraj

是的，你可以做得比這更好。嘗試遞歸思考（雖然你可以很容易地重構迭代解決方案。） – BPS

假設最終的結果將是一個整數R.應該由左到右弦上再掃描，你應該保持一個棧Z，和你從左至右掃描更新。當你在索引i處遇到'（'時，你應該將0推到S上。當你在索引i遇到'''時，你應該將R增加（T * （T + 1）/ 2），T是Z的頂部元素。然後，您應該彈出T，並將新的頂部元素增加1.

一旦掃描完成，您應該將R增加一更多的時間由（T *（T + 1）/ 2）計算，因爲在Z中仍然有一個元素T，我們最初放置。

使用堆棧Z的掃描應採取線性時間。下面是一個不太高效的Python實現，希望很容易理解。

def solve(s): 
    R = 0 
    Z = [0] 
    for i in range(0, len(s)): 
     if s[i] == '(': 
      Z.append(0) 
     else: 
      R += Z[-1] * (Z[-1] + 1)/2 
      Z = Z[:-1] 
      Z[-1] += 1 
    R += Z[-1] * (Z[-1] + 1)/2 
    return R

增量R背後的想法如下。基本上你保持連續相同級別的平衡字符串的數量，直到即將離開該級別。然後，當您即將進入更高級別時（即當我們知道時，將不會有任何其他同級別和連續子字符串，我們更新解決方案

T *（T + 1）/ 2可以理解，如果你考慮間隔有點不同，讓我們列舉從1到T連續的相同級別的平衡子串。現在，使用這些子串選擇一個平衡子串基本上是爲我們的更大的起點和終點如果我們選擇子字符串＃1作爲我們的起點，我們可以選擇其他子字符串作爲終點，＃2有（T-1）等等，基本上有T *（T + 1）/ 2個不同的時間間隔，我們可以選擇一個有效的balanged子串，這就是爲什麼我們通過該值增加R的原因。

我們應用於R的最終增量操作只是爲了不忽略最外層。

來源

2016-03-22 16:34:12 ilim

你的方法時間複雜度先生？ – suraj

@suraj你所要做的就是掃描字符串。如果你使用適當的堆棧（即不像使用像我這樣的列表），那麼你在循環的每次迭代中所做的所有操作都需要一段時間。因此，就字符串的長度而言，複雜度是線性的。 – ilim

真棒回答先生！ – suraj

我做了一個簡單的算法，可以解決您的問題。請注意，它不尋找嵌套平衡圓括號。

function TestAlgorithm(testString, resultCounter) 
{ 
    if (!resultCounter) 
     resultCounter = 0; 

    var startIndex = testString.indexOf('('); 

    if (startIndex === -1) 
     return resultCounter; 

    var endIndex = testString.indexOf(')', startIndex) 

    if (endIndex === -1) 
     return resultCounter; 

    var newTestString = testString.substring(endIndex); 

    return TestAlgorithm(newTestString, ++resultCounter); 
}

來源

2016-03-22 16:27:58 Mick

每個子那是在範圍上以「（」所以，我的非遞歸的方法是：

total = 0 
while string is not empty { 
    count valid substrings beginning here -- add to total 
    trim leading '(' and trailing ')' from string 
    trim leading ')' and trailing '(' from string if present 
}

count valid substrings beginning here可以通過用炭炭步，遞增計數器，當你看到做「（'，當你看到''時遞減）。當遞減結果爲零時，你在平衡子串的結束'）'處。

來源

2016-03-22 16:52:59 slim

帶有平衡括號的子串

回答

相關問題