LeetCode1047: 文字列内の隣接する重複項の削除

問題：

小文字からなる文字列 S が与えられます。重複項削除操作は、隣接する同じ文字のペアを選択して削除します。

S に対して重複項削除操作を繰り返し実行し、削除ができなくなるまで続けます。

すべての重複項削除操作が完了した後、最終的な文字列を返してください。答えは一意であることが保証されます。

例：

例：

<strong>入力：</strong>"abbaca"
<strong>出力：</strong>"ca"
<strong>説明：</strong>
例えば、"abbaca" では、"bb" を削除できます。これは、この時点で実行可能な唯一の削除操作です。その後、文字列 "aaca" を得ます。ここでは、"aa" のみが削除操作を実行できます。したがって、最終的な文字列は "ca" になります。

ヒント：

1. 1 <= S.length <= 20000
2. S は小文字の英字のみで構成されます。

解法の考え方：

文字列に複数の隣接する重複項がある場合、どの重複項を先に削除しても最終結果に影響しません。したがって、文字列を左から右へ順次処理できます。

隣接する重複項のペアを削除すると、新しい隣接する重複項が発生する可能性があります。例えば、"abba" から "bb" を削除すると、"aa" という新しい隣接する重複項が現れます。したがって、まだ削除されていない文字を保存する必要があります。明らかなデータ構造が浮かび上がります：スタック。文字列を走査するだけで、現在の文字がスタックのトップと同じであれば、貪欲にそれを消去し、そうでなければスタックに追加するだけです。

コード実装：

char* eliminateAdjacentDuplicates(char* inputStr) {
    int length = strlen(inputStr);
    char *stack = malloc(sizeof(char) * (length + 1));
    int stackSize = 0;
    
    for(int i = 0; i < length; i++) {
        if(stackSize > 0 && stack[stackSize - 1] == inputStr[i]) {
            stackSize--;
        } else {
            stack[stackSize++] = inputStr[i];
        }
    }
    
    stack[stackSize] = '\0';
    return stack;
}

LeetCode20: 有効な括弧

問題

'('、')'、'{'、'}'、'['、']' のみからなる文字列 s が与えられます。文字列が有効かどうかを判断してください。

有効な文字列は次の条件を満たす必要があります：

1. 左括弧は同じタイプの右括弧で閉じる必要があります。
2. 左括弧は正しい順序で閉じる必要があります。
3. 各右括弧には対応する同じタイプの左括弧があります。

例

例 1：

<strong>入力：</strong>s = "()"
<strong>出力：</strong>true

例 2：

<strong>入力：</strong>s = "()[]{}"
<strong>出力：</strong>true

例 3：

<strong>入力：</strong>s = "(]"
<strong>出力：</strong>false

ヒント：

• 1 <= s.length <= 104
• s は括弧 '()[]{}' のみで構成されます

解法の考え方

与えられた文字列 s を走査します。左括弧に遭遇した場合、後続の走査で同じタイプの右括弧で閉じられることを期待します。後から遭遇した左括弧が先に閉じられるため、この左括弧をスタックのトップに配置します。

右括弧に遭遇した場合、同じタイプの左括弧を閉じる必要があります。このとき、スタックのトップから左括弧を取り出し、それらが同じタイプの括弧であるか判断します。同じタイプでない場合、またはスタックに左括弧がない場合、文字列 s は無効であり、False を返します。

走査が終了した後、スタックに左括弧がない場合、文字列 s のすべての左括弧が閉じられていることを意味し、True を返します。そうでない場合は False を返します。

有効な文字列の長さは常に偶数であることに注意してください。したがって、文字列の長さが奇数の場合、後続の走査判断プロセスを省略して直接 False を返すことができます。

コード実装

bool checkParenthesesValidity(char* expression) {
    int exprLength = strlen(expression);
    
    char stack[exprLength];
    int topIndex = -1;

    for (int i = 0; i < exprLength; i++) {
        if (expression[i] == '(' || expression[i] == '[' || expression[i] == '{') {
            stack[++topIndex] = expression[i];
        } else {
            if (topIndex == -1)
                return false;

            char lastOpen;
            lastOpen = stack[topIndex--];

            if (expression[i] == ')' && lastOpen != '(')
                return false;
            if (expression[i] == ']' && lastOpen != '[')
                return false;
            if (expression[i] == '}' && lastOpen != '{')
                return false;
        }
    }

    if (topIndex != -1)
        return false;
    return true;
}