Etibarlı Mötərizələr Leetcode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Cisco Expedia Facebook Goldman Sachs google Intel LinkedIn microsoft Netflix Kahin Salesforce XidmətNow Spotify TCS VMware Yandex Zillow
Arista Networks Barclays Booking.com Dataminr Qalaq Sim tiktokBaxılıb 30

Problem bəyanat

The Etibarlı Mötərizələr LeetCode Həlli – “Etibarlı Mötərizələr” sizə yalnız simvollardan ibarət sətir verildiyini bildirir '('')''{''}''[' və ']'. Giriş sətirinin etibarlı sətir olub-olmadığını müəyyən etməliyik. Açıq mötərizələr eyni tip mötərizələrlə bağlanmalı və açıq mötərizələr eyni düzgün ardıcıllıqla bağlanmalıdırsa, sətir etibarlı sətir deyilir.

Misal:

Input:  s = "()"
Output: true

Explanation:

  • Açıq mötərizə '(' eyni tip bağlama mötərizəsi ilə bağlanır ')'.
Input:  s = "(]"
Output: false

Explanation:

  • Açıq mötərizə '(' eyni tip bağlama mötərizəsi ilə bağlanmır.

Yanaşma

Idea:

  1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir Qalaq.
  2. Biz qoruyacağıq a simvol yığını və hər dəfə açılış mötərizəmiz olduqda, yığının həmin mövqeyində eyni tip bağlama mötərizəsini itələyirik.
  3. Yığın olduqda bağlanan mötərizə ilə qarşılaşdıqda boş deyil və yığının yuxarı simvolu sətrin cari simvolu ilə eyni olmalıdır. Əgər Bəli, sonra davam edin, əks halda, burada yalan qaytarın.
  4. Sətin bütün simvollarını emal etdikdən sonra, olub olmadığını yoxlayın qalaq boşdur, doğru qayıt bu, giriş sətirinin etibarlı mötərizə sətri olduğunu bildirir, əks halda, yalan qayıt.

Kodu

Etibarlı Mötərizələr Leetcode C++ Həlli:

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(auto& c:s){
            if(c=='('){
                st.push(')');
            }
            else if(c=='{'){
                st.push('}');
            }
            else if(c=='['){
                st.push(']');
            }
            else if(st.empty() or st.top()!=c){
                return false;
            }
            else{
                st.pop();
            }
        }
        return st.empty()==true;
    }
};

Etibarlı Mötərizələr Leetcode Java Həlli:

class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<Character>();
        for(char c:s.toCharArray()){
            if(c=='('){
          st.push(')');
            }
        else if(c=='{'){
          st.push('}');
            }
        else if(c=='['){
          st.push(']');
            }
            else if(st.empty() || st.pop()!=c){
                return false;
            }
        }
        return st.isEmpty();
    }
}

Etibarlı Mötərizələr üçün Mürəkkəblik Təhlili Leetcode Həlli

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (N) çünki biz bütün giriş sətirini tam olaraq bir dəfə keçirik, burada N = sətirin ümumi uzunluğu.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (N). Ən pis halda O(N) yerini tutan simvolları saxlamaq üçün yığından istifadə edirik.

Translate »