1. 隣接する重複文字の削除

問題概要

文字列内で連続する同じ文字をすべて削除した結果を返します。

解法のポイント

各文字を順番に確認し、直前の文字と比較して同じであれば削除、異なれば保持します。この操作はスタックの「後入れ先出し」特性と一致します。実際にスタックオブジェクトを使用すると最終的な文字列構築が面倒なため、配列を使ってスタック動作をシミュレートします。

実装例

class Solution {
    public String removeDuplicates(String s) {
        char[] stack = new char[s.length()];
        int top = -1;
        
        for (char c : s.toCharArray()) {
            if (top >= 0 && stack[top] == c) {
                top--;
            } else {
                stack[++top] = c;
            }
        }
        
        return new String(stack, 0, top + 1);
    }
}

2. バックスペースを含む文字列の比較

問題概要

'#'文字をバックスペースとして解釈し、最終的な文字列が2つの入力で等しいか判定します。

解法のポイント

バックスペースは直前の有効な文字を削除する操作です。文字列を先頭から走査し、通常文字は保持、バックスペースは削除操作を実行します。2つの文字列を同様に処理してから比較します。

実装例

class Solution {
    public boolean backspaceCompare(String s, String t) {
        return buildFinalString(s).equals(buildFinalString(t));
    }
    
    private String buildFinalString(String str) {
        StringBuilder result = new StringBuilder();
        for (char ch : str.toCharArray()) {
            if (ch == '#') {
                if (result.length() > 0) {
                    result.setLength(result.length() - 1);
                }
            } else {
                result.append(ch);
            }
        }
        return result.toString();
    }
}

3. 基本電算機 II

問題概要

加減乗除のみからなる式文字列を計算します（括弧は含まれません）。

解法のポイント

乗除算は加減算より優先度が高いため、即座に計算します。加減算は後回しにするため、正負の数値としてスタックに保存します。数字は複数桁になる可能性があるため、桁ごとに処理します。

実装例

class Solution {
    public int calculate(String expression) {
        Deque<Integer> numberStack = new ArrayDeque<>();
        char lastOperator = '+';
        char[] chars = expression.toCharArray();
        int i = 0;
        
        while (i < chars.length) {
            if (chars[i] == ' ') {
                i++;
                continue;
            }
            
            if (Character.isDigit(chars[i])) {
                int num = extractNumber(chars, i);
                while (i < chars.length && Character.isDigit(chars[i])) i++;
                
                switch (lastOperator) {
                    case '+': numberStack.push(num); break;
                    case '-': numberStack.push(-num); break;
                    case '*': numberStack.push(numberStack.pop() * num); break;
                    case '/': numberStack.push(numberStack.pop() / num); break;
                }
            } else {
                lastOperator = chars[i];
                i++;
            }
        }
        
        return numberStack.stream().reduce(0, Integer::sum);
    }
    
    private int extractNumber(char[] chars, int start) {
        int value = 0;
        int idx = start;
        while (idx < chars.length && Character.isDigit(chars[idx])) {
            value = value * 10 + (chars[idx] - '0');
            idx++;
        }
        return value;
    }
}

4. エンコード文字列のデコード

問題概要

数字とブラケットでエンコードされた文字列を展開します（例：3[a2[c]] → "accaccacc"）。

解法のポイント

数字と文字列を別々のスタックで管理します。'['が現れたら新しい文字列コンテキストを開始し、']'が現れたら数字スタックから繰り返し回数を取得して文字列スタックのトップを展開します。入れ子構造に対応するため、スタックの底に空の文字列を配置します。

実装例

class Solution {
    public String decodeString(String encoded) {
        Deque<Integer> repeatCounts = new ArrayDeque<>();
        Deque<StringBuilder> stringBuilders = new ArrayDeque<>();
        stringBuilders.push(new StringBuilder());
        
        char[] arr = encoded.toCharArray();
        int pos = 0;
        
        while (pos < arr.length) {
            if (Character.isDigit(arr[pos])) {
                int count = parseNumber(arr, pos);
                while (pos < arr.length && Character.isDigit(arr[pos])) pos++;
                repeatCounts.push(count);
            } else if (arr[pos] == '[') {
                stringBuilders.push(new StringBuilder());
                pos++;
            } else if (arr[pos] == ']') {
                StringBuilder inner = stringBuilders.pop();
                int times = repeatCounts.pop();
                StringBuilder outer = stringBuilders.peek();
                outer.append(String.valueOf(inner).repeat(times));
                pos++;
            } else {
                stringBuilders.peek().append(arr[pos]);
                pos++;
            }
        }
        
        return stringBuilders.pop().toString();
    }
    
    private int parseNumber(char[] arr, int start) {
        int num = 0;
        int idx = start;
        while (idx < arr.length && Character.isDigit(arr[idx])) {
            num = num * 10 + (arr[idx] - '0');
            idx++;
        }
        return num;
    }
}

5. スタック操作シーケンスの検証

問題概要

プッシュシーケンスとポップシーケンスが有効なスタック操作かどうかを判定します。

解法のポイント

プッシュシーケンスを順番にスタックに積みながら、スタックのトップがポップシーケンスの先頭と一致する限りポップを繰り返します。すべての要素を処理した後、スタックが空であれば有効なシーケンスです。

実装例

class Solution {
    public boolean validateStackSequences(int[] pushSeq, int[] popSeq) {
        Deque<Integer> stack = new ArrayDeque<>();
        int popPointer = 0;
        
        for (int value : pushSeq) {
            stack.push(value);
            while (!stack.isEmpty() && stack.peek() == popSeq[popPointer]) {
                stack.pop();
                popPointer++;
            }
        }
        
        return stack.isEmpty();
    }
}