20. 有効な括弧

この問題は、与えられた文字列の括弧が有効かどうかを判断する必要があります。有効な括弧の定義は、全ての開き括弧に対応する閉じ括弧があり、正しい順序と埋め込みになっていることです。

解決方法：この問題は、スタック（堆積構造）を使用して効率的に解決できます。スタックに開き括弧をプッシュし、閉じ括弧が出現した際にはスタックの先頭要素とマッチングを行います。マッチングしない場合は、文字列が有効ではありません。

境界条件：文字列の長さが0、奇数、または1である場合は、有効ではありません。

            // 時間計算量：O(n), 空間計算量：O(n)
            class Solution {
                public boolean isValid(String s) {
                    // 開き括弧をスタックにプッシュし、閉じ括弧が出現した際にはスタックの先頭要素と比較する
                    if (s.length() == 0 || s.length() == 1 || s.length() % 2 != 0) {
                        return false;
                    }
                    
                    char[] arr = s.toCharArray();
                    Map map = new HashMap<>();
                    map.put(')', '(');
                    map.put(']', '[');
                    map.put('}', '{');
                    
                    int top = -1;
                    for (int i = 0; i < arr.length; i++) {
                        if (map.containsKey(arr[i])) {
                            if (top >= 0 && arr[top] == map.get(arr[i])) {
                                top--;
                            } else {
                                return false;
                            }
                        } else {
                            arr[++top] = arr[i];
                        }
                    }
                    
                    return top == -1;
                }
            }
        

1047. 文字列内のすべての隣接重複を削除

この問題は、文字列内の全ての隣接する重複要素を削除する必要があります。例えば、文字列 "abccba" は削除後、空文字列になります。

解決方法：スタックを使用して、隣接する重複要素を削除します。文字列を配列に変換し、配列の一部をスタックとして使用します。要素をプッシュする際、スタックの先頭要素と比較し、重複している場合は削除します。

            // 時間計算量：O(n), 空間計算量：O(n)
            class Solution {
                public String removeDuplicates(String s) {
                    char[] arr = s.toCharArray();
                    int top = -1;
                    
                    for (int i = 0; i < arr.length; i++) {
                        if (top >= 0 && arr[i] == arr[top]) {
                            top--;
                        } else {
                            arr[++top] = arr[i];
                        }
                    }
                    
                    return new String(arr, 0, top + 1);
                }
            }