Codility支架挑戰性能問題

Question

嘗試一個簡單的編碼挑戰（檢查一串{}字符是否合格）我已經陷入了困境，因爲我的解決方案的性能得分很差，甚至超過了一些他們的測試用例。

，規格爲「返回1，如果很好地形成。否則爲0」：

class Solution { 
public int solution(String S) { 

    Deque<String> stack = new LinkedList<String>(); 
    while (S.length() > 0) { 
     String firstChar = S.substring(0, 1); 
     if (isOpenBracket(firstChar)) { 
      stack.addFirst(firstChar); 
     } 
     else { 
      String matchingOpen = closedToOpen(firstChar); 
      if (matchingOpen == null) return 0; 

      String topOfStack = stack.pollFirst(); 
      if (!matchingOpen.equals(topOfStack)) { 
       return 0; 
      } 
     } 
     S = S.substring(1); 
    } 
    return stack.isEmpty() ? 1 : 0; 
} 

public boolean isOpenBracket(String s) { 
    return ("{".equals(s) || "[".equals(s) || "(".equals(s)); 
} 

public String closedToOpen(String closed) { 
    if ("}".equals(closed)) return "{"; 
    if ("]".equals(closed)) return "["; 
    if (")".equals(closed)) return "("; 
    return null; 
} 
} 

起初我以爲的罪魁禍首是addfirst僅/ pollFirst實際上附加在鏈表的盡頭，但是這不是該案例（改變添加/ pollLast實際上產生相同的分數配置文件）。

我可以看到，使用字符，而不是字符串將加快東西，但我不認爲它太不夠有關超時測試（預計時間< 3秒，運行時間> 8秒）...

我最後的猜測是輔助方法會在每次調用時重新分配常量...但這仍然是如此大的影響？

任何想法？

Answer 1

問題是調用長度爲n的字符串的子字符串的成本爲O(n)，因爲它會生成副本。不要一直複製字符串，而是要保留一個字符串並訪問每個字符。