有效的括號字符串


難度級別
經常問 亞馬遜 Facebook 神諭

在有效的括號內 問題,我們給了一個包含'(,)'和'*',檢查字符串是否平衡,如果'*可以替換為(',')'或一個空字符串。

範例檔案

輸入
“()”
產量

輸入
“ *)”
產量

輸入
“(*))”
產量

有效括號字符串的幼稚方法

*'可以採用三個可能的值,嘗試所有這些值,如果有任何有效的平衡字符串,則當前字符串有效。

  1. 遍歷給定的字符串。
  2. 遞歸替換'*與“(',')'和空字符串。
  3. 如果任何組合是平衡字符串,則給定的字符串是平衡的。

考慮一個示例“ *)”,

有效的括號字符串

有效括號字符串的JAVA代碼

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));
    }
}

有效括號字符串的C ++代碼

#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

複雜度分析

時間複雜度= O(n * 3n
空間複雜度= O(3n), 由於遞歸
其中n是給定字符串中的字符數。

有效括號字符串的最佳方法

對於給定字符串的每個字符,計數到此為止的最小和最大方括號數。

  1. 開括號將最小值和最大值加1。
  2. 尖括號將最小值和最大值減小1,最小值不能為負。
  3. 星號(*)將最小值減少1,並將最大值增加1。
  4. 如果最大值在任何時候變為負值,則字符串不平衡。

如果方括號的下限值為0,則該字符串有效。

考慮字符串“(***)

  • '(':將最小值和最大值增加1 {索引0}(最小值= 1,最大值= 1)
  • '*':將最小值減小1,將最大值減小1 {索引1、2和3}(最小值= 0,最大值= 4)
  • '):將最小值和最大值減小1 {索引4}(最小值= 0且最大值= 3)

遍歷結束時最小值為0,因此該字符串有效。

JAVA代碼

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 ++代碼

#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

有效括號字符串的複雜度分析

時間複雜度= O(N) 
空間複雜度= O(1)
其中n是給定字符串中的字符數。

參考