ວົງເລັບທີ່ຖືກຕ້ອງ  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ ພະຍຸຫິມະ Bloomberg ByteDance Expedia ເຟສບຸກ Goldman Sachs ກູໂກ IBM lyft Microsoft Oracle Spotify Zillow
BufferedOutputStream string

In ວົງເລັບທີ່ຖືກຕ້ອງ ບັນຫາທີ່ພວກເຮົາໄດ້ໃຫ້ string ບັນຈຸພຽງແຕ່ຕົວອັກສອນ '(', ')', '{', '}', '[' ແລະ ']', ກຳ ນົດວ່າສາຍປ້ອນຂໍ້ມູນຖືກຕ້ອງຫຼືບໍ່.

ລະຫັດປ້ອນເຂົ້າແມ່ນຖືກຕ້ອງຖ້າ:

  1. ວົງເລັບເປີດຕ້ອງຖືກປິດດ້ວຍວົງເລັບປະເພດດຽວກັນ.
    • ()
    • []
    • {}
  2. ວົງເລັບເປີດຕ້ອງຖືກປິດໃນລະບຽບທີ່ຖືກຕ້ອງ.
    • ()][ ບໍ່​ຖືກ​ຕ້ອງ
    • () {[]} ຖືກຕ້ອງ
    • [() {}] ຖືກຕ້ອງ

ຍົກຕົວຢ່າງ  

ການປ້ອນຂໍ້ມູນ: str =“ [] {() ()}”

ຜົນຜະລິດ: ສະຕິງທີ່ປະກອບມີວົງເລັບທີ່ຖືກຕ້ອງ.

ສູດການຄິດໄລ່ ສຳ ລັບວົງເລັບທີ່ຖືກຕ້ອງ  

n: ຄວາມຍາວຂອງຊ່ອຍແນ່

str: ສາຍເຂົ້າ

  1. ປະກາດແລະເລີ່ມຕົ້ນ stack S.
  2. ດໍາເນີນການ loop ສຸດ i ຈາກ 0 ເຖິງ n.
    1. ຖ້າ str [i] ແມ່ນວົງເລັບເປີດ, ຫຼັງຈາກນັ້ນຍູ້ str [i] ໃນຊັ້ນວາງ.
    2. ຖ້າ str [i] ແມ່ນວົງເລັບປິດ, ຫຼັງຈາກນັ້ນມີຄວາມເປັນໄປໄດ້ສອງຢ່າງ:
      • ຖ້າວົງເລັບດ້ານເທິງທີ່ມີຢູ່ໃນ stack ແມ່ນວົງເລັບເປີດຂອງປະເພດດຽວກັນ, ຫຼັງຈາກນັ້ນໃຫ້ເປີດສ່ວນເທິງຂອງສ່ວນປະກອບ.
      • ອື່ນ, ກັບຄືນມາບໍ່ຖືກຕ້ອງ.
  3. ກັບຄືນ S.empty ().

ຂັ້ນຕອນການເຮັດວຽກຂັ້ນຕອນໂດຍຂັ້ນຕອນ  

str = [{} ()]

n = 6

ຂັ້ນຕອນທີ 1: ພວກເຮົາໄດ້ຮັບວົງເລັບເປີດ [, ເພາະສະນັ້ນການຊຸກຍູ້ [ໃນ stack.

ຂັ້ນຕອນທີ 2: ພວກເຮົາໄດ້ຮັບວົງເລັບເປີດ {, ເພາະສະນັ້ນການຊຸກຍູ້ {ໃນ stack.

ວົງເລັບທີ່ຖືກຕ້ອງPin

ຂັ້ນຕອນທີ 3: ພວກເຮົາໄດ້ຮັບວົງເລັບປິດ} ແລະດ້ານເທິງຂອງ stack ແມ່ນ {, ເພາະສະນັ້ນຈຶ່ງປະຕິບັດງານ pop ໃນ stack.

ວົງເລັບທີ່ຖືກຕ້ອງPin

 

ຂັ້ນຕອນທີ 4: ພວກເຮົາໄດ້ຮັບວົງເລັບເປີດ (, ເພາະສະນັ້ນການຊຸກຍູ້ (ໃນ stack.

ເບິ່ງ
ຈັດລະບົບສາຍເຊືອກຄືນ ໃໝ່

Pin

ຂັ້ນຕອນທີ 5: ພວກເຮົາໄດ້ຮັບວົງເລັບປິດ) ແລະດ້ານເທິງຂອງ stack ແມ່ນ (, ເພາະສະນັ້ນຈຶ່ງເຮັດການປະຕິບັດງານ pop ໃນ stack.

 

ວົງເລັບທີ່ຖືກຕ້ອງPin
ວົງເລັບທີ່ຖືກຕ້ອງ

ຂັ້ນຕອນທີ 6: ພວກເຮົາໄດ້ຮັບວົງເລັບປິດ] ແລະດ້ານເທິງຂອງ stack ແມ່ນ [, ເພາະສະນັ້ນຈຶ່ງເຮັດວຽກ pop ຢູ່ເທິງ stack.

ວົງເລັບທີ່ຖືກຕ້ອງPin

ການຈັດຕັ້ງປະຕິບັດ ສຳ ລັບວົງເລັບທີ່ຖືກຕ້ອງ  

ໂປຣແກຣມ C ++ ສຳ ລັບ parentheses ທີ່ຖືກຕ້ອງ

#include<bits/stdc++.h>
using namespace std;
bool isValid(string s) {
    stack<char> bracket;
    for (char& c : s) {
        switch (c) {
            case '(': bracket.push(c); break;
            case '{': bracket.push(c); break;
            case '[': bracket.push(c); break;
            case ')': if (bracket.empty() || bracket.top()!='(') return false; else bracket.pop(); break;
            case '}': if (bracket.empty() || bracket.top()!='{') return false; else bracket.pop(); break;
            case ']': if (bracket.empty() || bracket.top()!='[') return false; else bracket.pop(); break;
            default: ; 
        }
    }
    return bracket.empty() ;
}
int main(){
    string s = "[[]{}]()";
    bool check = isValid(s);
    if(check){
        cout<<"The given string contains valid parentheses.";
    }
    else{
        cout<<"The given string contains invalid parentheses.";
    }
}
The given string contains valid parentheses.

ໂປແກຼມ JAVA ສຳ ລັບ Valid Parentheses

import java.util.*; 
public class Main
{
    public static boolean isValid(String s) {
        Stack<Character> bracket = new Stack<>();
        for (char c : s.toCharArray()) {
             switch (c) {
                case '(': bracket.push(c); break;
                case '{': bracket.push(c); break;
                case '[': bracket.push(c); break;
                case ')': if (bracket.empty() || bracket.peek()!='(') return false; else bracket.pop(); break;
                case '}': if (bracket.empty() || bracket.peek()!='{') return false; else bracket.pop(); break;
                case ']': if (bracket.empty() || bracket.peek()!='[') return false; else bracket.pop(); break;
                default: ; 
            }
        }
        return bracket.isEmpty();
    }
  public static void main(String[] args) {
      String s = "{}[)(]";
      boolean check = isValid(s);
          if(check){
                System.out.println("The given string contains valid parentheses.");
            }
            else{
                System.out.println("The given string contains invalid parentheses.");
            }
  }
}
The given string contains invalid parentheses.

ຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (n)

ເບິ່ງ
ຄຳ ສັບ K ເລື້ອຍໆ

ບ່ອນທີ່ n ແມ່ນຄວາມຍາວຂອງສະຕິງທີ່ຖືກມອບໃຫ້ໃນຂະນະທີ່ພວກເຮົາ ກຳ ລັງຜ່ານເຊືອກທີ່ໃຫ້ໄວ້ເທື່ອດຽວ.

ການປະຕິບັດງານ pop (), ດ້ານເທິງ () ແລະຍູ້ () ໃນ stack ແມ່ນໃຊ້ເວລາຄົງທີ່.

ຄວາມສັບສົນໃນອະວະກາດ

O (n)

ດັ່ງທີ່ພວກເຮົາສາມາດ ນຳ ໃຊ້ພື້ນທີ່ເພີ່ມເຕີມຂອງ stack ແລະໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດ, ຂະ ໜາດ ຂອງ stack ກໍ່ສາມາດ n / 2

ເອກະສານ