Etibarlı parantez simli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Facebook Kahin
SimBaxılıb 104

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Etibarlı mötərizədə sim problem olan bir simli verdik '(", ")'və'*', sətrin tarazlı olub olmadığını yoxlayın.'*'ilə əvəz edilə bilər'(',')'və ya boş bir simli.

Nümunələr

Input
"()"
Buraxılış
doğru

Input
"*)"
Buraxılış
doğru

Input
"(*))"
Buraxılış
doğru

Valid Parentez Simli üçün sadəlövh yanaşma

"*'üç mümkün dəyər götürə bilər, bütün bu dəyərləri sınayın, əgər balanslaşdırılmış bir ciziq varsa, cari sətir etibarlıdır.

  1. Verilən simli keçin.
  2. Rekursiv şəkildə dəyişdirin '*'ilə'(',')'və boş simli.
  3. Hər hansı bir birləşmə balanslaşdırılmış bir simdirsə, verilmiş simli balanslaşdırılmışdır.

Bir nümunəyə baxaq, “*)”,

Etibarlı parantez simliPin

Valid Parentez Simli üçün JAVA Kodu

public class ValidParanthesisString {
    private static boolean ans;

    private static boolean isValid(String str) {
        // Initialise ans as false
        ans = false;
        // Recur and try all the combinations possible for the string
        recurStr(new StringBuilder(str), 0);
        return ans;
    }

    private static void recurStr(StringBuilder str, int i) {
        if (i == str.length()) {
            // check validity of the string, as it is fully formed when i = str.length()
            ans |= checkValidity(str);
        } else if (str.charAt(i) == '*') {
            // Replace * with (
            str.setCharAt(i, '(');
            recurStr(str, i + 1);
            // Replace * with )
            str.setCharAt(i, ')');
            recurStr(str, i + 1);
            // replace * with empty string
            str.setCharAt(i, ' ');
            recurStr(str, i + 1);
        } else {
            // If the current character is not * continue for next character
            recurStr(str, i + 1);
        }
    }
    
    // Function to check if given string is balanced or not
    private static boolean checkValidity(StringBuilder str) {
        int bal = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                bal++;
            } else if (str.charAt(i) == ')') {
                bal--;
            }
            if (bal < 0) {
                break;
            }
        }

        return bal == 0;
    }
    
    public static void main(String[] args) {
        // Example 1
        String str = "()";
        System.out.println(isValid(str));
        
        // Example 2
        str = "(*)";
        System.out.println(isValid(str));
        
        // Example 3
        str = "(*))";
        System.out.println(isValid(str));
    }
}

Valid Parentez Simli üçün C ++ Kodu

#include <iostream>
using namespace std;

bool ans;

// Function to check if given string is balanced or not
bool checkValidity(string str) {
    int bal = 0;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(') {
            bal++;
        } else if (str[i] == ')') {
            bal--;
        }
        if (bal < 0)
            break;
    }
    return (bal == 0);
}

void recurStr(string str, int i) {
    if (i == str.size()) {
        // check validity of the string, as it is fully formed when i = str.length()
        ans |= checkValidity(str);
    } else if (str[i] == '*') {
        // Replace * with (
        str[i] = '(';
        recurStr(str, i + 1);
        // Replace * with )
        str[i] = ')';
        recurStr(str, i + 1);
        // replace * with empty string
        str[i] = ' ';
        recurStr(str, i + 1);
    } else {
        // If the current character is not * continue for next character
        recurStr(str, i + 1);
    }
}

bool isValid(string str) {
    // Initialise ans as false
    ans = false;
    
    // Recur and try all the combinations possible for the string
    recurStr(str, 0);
    
    return ans;
}

int main() {
  string str = "()";
    if (isValid(str)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    str = "(*)";
    if (isValid(str)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 3
    str = "(*))";
    if (isValid(str)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
  return 0;
}
true
true
true

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (n * 3n
Kosmik Mürəkkəblik = O (3n), rekursiyaya görə
burada n - verilən sətirdəki simvolların sayı.

Valid Parentez Simli üçün optimal yanaşma

Verilən sətrin hər bir simvolu üçün bu nöqtəyə qədər minimum və maksimum açıq mötərizə sayın.

  1. Açıq bir mötərizə minimum və maksimum dəyəri 1 artırır.
  2. Yaxın bir mötərizə minimum və maksimum dəyəri 1 azaldır, aşağı dəyər mənfi ola bilməz.
  3. Ulduz (*) minimum dəyəri 1 azaldır və maksimum dəyəri 1 artırır.
  4. Maksimum dəyər istənilən nöqtədə mənfi olursa, sətir balanslaşdırılmır.

Açıq mötərizənin aşağı dəyəri 0 olarsa, sətir etibarlıdır.

misal

Sətri düşünək “(***)"

  • '(': Minimum və maksimumu 1 {İndeks 0} artırır (minimum = 1, maksimum = 1)
  • '*': Minimumu 1-ə endirir və maksimumu 1-ə artırır {İndeks 1, 2 və 3} (minimum = 0 və maksimum = 4)
  • '): Minimum və maksimumu 1 {İndeks 4} azaldır (minimum = 0 və maksimum = 3)

keçidin sonunda minimum 0, buna görə də sətir etibarlıdır.

JAVA Kodu

public class ValidParanthesisString {
    private static boolean isValid(String str) {
        // Initialise minimum and maximum as 0
        int minimum = 0, maximum = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                // Open bracket increases minimum and maximum by 1
                minimum++;
                maximum++;
            } else if (str.charAt(i) == ')') {
                // Close bracket decreases minimum and maximum by 1
                minimum--;
                maximum--;
            } else {
                // asterisk(*) decreases minimum by 1 and increases maximum by 1
                minimum--;
                maximum++;
            }
            // If maximum becomes less than 0, string is not balanced
            if (maximum < 0)
                return false;
            // minimum cannot be less than 0
            minimum = Math.max(minimum, 0);
        }
        
        // If minimum is 0, then string is balanced
        return minimum == 0;
    }
    
    public static void main(String[] args) {
        // Example 1
        String str = "()";
        System.out.println(isValid(str));

        // Example 2
        str = "(*)";
        System.out.println(isValid(str));

        // Example 3
        str = "(*))";
        System.out.println(isValid(str));
    }
}

C ++ kodu

#include <iostream>
using namespace std;

bool isValid(string str) {
    // Initialise minimum and maximum as 0
    int minimum = 0, maximum = 0;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(') {
            // Open bracket increases minimum and maximum by 1
            minimum++;
            maximum++;
        } else if (str[i] == ')') {
            // Close bracket decreases minimum and maximum by 1
            minimum--;
            maximum--;
        } else {
            // asterisk(*) decreases minimum by 1 and increases maximum by 1
            minimum--;
            maximum++;
        }
        // If maximum becomes less than 0, string is not balanced
        if (maximum < 0)
            return false;
        // minimum cannot be less than 0
        minimum = std::max(minimum, 0);
    }
    // If minimum is 0, then string is balanced
    return (minimum == 0);
}

int main() {
  string str = "()";
    if (isValid(str)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    str = "(*)";
    if (isValid(str)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 3
    str = "(*))";
    if (isValid(str)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
  return 0;
}
true
true
true

Valid Parentez Simli üçün Mürəkkəblik Analizi

Zaman Mürəkkəbliyi = O (n) 
Kosmik Mürəkkəblik = O (1)
burada n - verilən sətirdəki simvolların sayı.

References

Crack Sistemi Dizayn Müsahibələri
Translate »