Решение задачи с действительными круглыми скобками в Dart


Вопрос

Дана строка s, содержащая только символы ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ и ‘]’,
определите, является ли входная строка допустимой.

Входная строка является допустимой, если:

Открытые скобки должны быть закрыты скобками того же типа.
Открытые скобки должны быть закрыты в правильном порядке.

Пример 1:

Вход: s = «()»
Выход: true

Пример 2:

Ввод: s = «()[]{}»
Выход: true

Пример 3:

Ввод: s = «(]»
Выход: false

Ограничения:

1 <= s.length <= 104
s состоит только из круглых скобок ‘()[]{}’.

Напоминание:-

Работают только два решения
1:- Класс B
2:- Класс E

Другие решения не работают в некоторых тестах, но на них стоит обратить внимание, как на способ достижения одной цели другим способом.


class A {
  // Almost Working
  bool isValid(String s) {
    if (s.isEmpty) return true;
    s.split("");

    List<String> parenthesisStack = [];
    for (var i = 0; i < s.length; i++) {
      if (s[i] == "(" ||
          s[i] == "{" ||
          s[i] == "[" && parenthesisStack.isEmpty) {
        return false;
      } else if (s[i] == "(" && parenthesisStack.last == ")" ||
          s[i] == "{" && parenthesisStack.last == "}" ||
          s[i] == "[" && parenthesisStack.last == "]") {
        parenthesisStack.removeLast();
      } else {
        parenthesisStack.add(s[i]);
      }
    }

    return parenthesisStack.length == 0;
  }
}
Вход в полноэкранный режим Выход из полноэкранного режима

Рабочее решение

class B {
  bool isValid(String s) {
    // map of parenthesis that we are checking  basically
    Map<String, String> parenthesis = <String, String>{
      ")": "(",
      "}": "{",
      "]": "[",
    };

    // lis to  save the values inside
    List<String> list = <String>[];

    // for loop to check the every entered item in string
    for (String item in s.split("")) {
      // checking  if the entered string contain the values that inside are same
      if (parenthesis.containsKey(item)) {
        // if the it's zero and length is less than zero or negative
        // OR the it is not same aas the parenthesis  than we will return false
        if (list.length == 0 || list[list.length - 1] != parenthesis[item])
          return false;
        else {
          // removing the last values
          list.removeLast();
        }
      } else {
        // than adding to the list
        list.add(item);
      }
    }
    // if the entered value is empty than it will be false if not than it
    // it will  be true
    return list.length == 0;
  }
}

Войти в полноэкранный режим Выйти из полноэкранного режима
class D {
  // So Close to Working
  bool isValid(String s) {
    int braces = 0;
    int sBrackets = 0;
    int rBrackets = 0;
    for (var i in s.split('')) {
      switch (i) {
        case ('{'):
          braces++;
          break;
        case ('}'):
          braces--;
          break;
        case ('('):
          rBrackets++;
          break;
        case (')'):
          rBrackets--;
          break;
        case ('['):
          sBrackets++;
          break;
        case (']'):
          sBrackets--;
          break;
      }
    }
    return (braces == 0) & (sBrackets == 0) & (rBrackets == 0);
  }
}
Войти в полноэкранный режим Выйти из полноэкранного режима

Второе рабочее решение


class E {
  bool isValid(String s) {
    List<String> stack = <String>[];

    for (var i = 0; i < s.length; i++) {
      if ('([{'.contains(s[i])) {
        stack.add(s[i]);
      } else {
        if (s[i] == ')' &&
            stack.length != 0 &&
            stack[stack.length - 1] == '(') {
          stack.removeLast();
        } else if (s[i] == ']' &&
            stack.length != 0 &&
            stack[stack.length - 1] == '[') {
          stack.removeLast();
        } else if (s[i] == '}' &&
            stack.length != 0 &&
            stack[stack.length - 1] == '{') {
          stack.removeLast();
        } else {
          return false;
        }
      }
    }

    return stack.length == 0;
  }

Войти в полноэкранный режим Выйти из полноэкранного режима

Время выполнения: 330 мс, быстрее, чем 66,67% онлайн-представлений Dart для Valid Parentheses.
Использование памяти: 140,4 МБ, меньше, чем в 100,00% случаев применения Dart в Интернете для программы Valid Parentheses.

Оцените статью
devanswers.ru
Добавить комментарий