1003. Check If Word Is Valid After Substitutions

leetcode medium

#csharp#leetcode#medium#stack#string#tree#two-pointers

Task

Дана строка s, определите, является ли она допустимой. Строка s допустима, если, начиная с пустой строки t = "", вы можете преобразовать t в s, выполнив следующую операцию любое количество раз: вставить строку "abc" в любую позицию в t. Более формально, t становится tleft + "abc" + tright, где t == tleft + tright. Обратите внимание, что tleft и tright могут быть пустыми. Верните true, если s - допустимая строка, иначе верните false.

Пример:

Input: s = "aabcbc"

Output: true

C# solution

matched/original

public class Solution {
    public bool IsValid(string s) {
        if (s.Length % 3 != 0) return false;
        Stack<char> stack = new Stack<char>();
        foreach (char ch in s) {
            if (ch == 'c') {
                if (stack.Count < 2 || stack.Pop() != 'b' || stack.Pop() != 'a') {
                    return false;
                }
            } else {
                stack.Push(ch);
            }
        }
        return stack.Count == 0;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool IsValid(string s) {
        if (s.size() % 3 != 0) return false;
        stack<char> stack = new stack<char>();
        foreach (char ch in s) {
            if (ch == 'c') {
                if (stack.size() < 2 || stack.pop() != 'b' || stack.pop() != 'a') {
                    return false;
                }
            } else {
                stack.push(ch);
            }
        }
        return stack.size() == 0;
    }
}

Java solution

matched/original

public class Solution {
    public boolean isValid(String s) {
        if (s.length() % 3 != 0) return false;

        Stack<Character> stack = new Stack<>();
        for (char ch : s.toCharArray()) {
            if (ch == 'c') {
                if (stack.size() < 2 || stack.pop() != 'b' || stack.pop() != 'a') {
                    return false;
                }
            } else {
                stack.push(ch);
            }
        }

        return stack.isEmpty();
    }
}

JavaScript solution

matched/original

class Solution {
    isValid(s) {
        if (s.length % 3 !== 0) return false;

        const stack = [];
        for (const char of s) {
            if (char === 'c') {
                if (stack.length < 2 || stack.pop() !== 'b' || stack.pop() !== 'a') {
                    return false;
                }
            } else {
                stack.push(char);
            }
        }

        return stack.length === 0;
    }
}

Explanation

Algorithm

Проверка допустимости длины строки:

Проверьте, что длина строки s кратна 3. Если нет, верните false.

Использование стека для проверки:

Инициализируйте пустой стек. Проходите по каждому символу строки s.

Если текущий символ является 'c', проверьте, что два предыдущих символа в стеке - это 'b' и 'a' соответственно. Если это так, удалите 'b' и 'a' из стека. Если нет, верните false.

Если текущий символ не 'c', добавьте его в стек.

Проверка остатка стека:

В конце, если стек пуст, верните true. Иначе верните false.

😎