Leetcode -678- valid parenthesis string

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

Given a string containing only three types of characters :(,) and *, write a function to verify that the string is a valid string. Valid strings have the following rules:

Any open parenthesis (must have corresponding close parenthesis). Any closing parenthesis) must have a corresponding opening parenthesis (. Open parenthesis (must precede the corresponding close parenthesis). * can be treated as a single close parenthesis), or a single open parenthesis (, or an empty string. An empty string is also considered a valid string. Example 1:

Input: "()" Output: TrueCopy the code

Example 2:

Input: "(*)" Output: TrueCopy the code

Example 3:

Input: "(*))" output: TrueCopy the code

Note:

The string size will be in the range of [1,100].

Idea 1: Dynamic planning

• In fact, when you do string matching in the first place you probably think about doing it on the stack
• A stack solution is also presented later in this article
• But this kind of problem is actually a lot easier to solve dp
• So the first thing you’re going to think about when you see parenthesis matching like this is dynamic programming, not stack manipulation
• There are fewer loading and unloading operations, slightly reducing the cost of understanding
• There are two ideas of dynamic programming in this problem, the first one is easier to understand and think of
• The equation dp[I][j] is defined to indicate whether the string matching rule is satisfied from subscript I to subscript j
• We can find that there are several cases to consider
  • S.charat (I) == * dp[I][I] = true
  • dp[i][j] = (s.charAt(i+1)=='(‘||s.charAt(i+1)==’*’)&& (s.charAt(j-1)==’)’||s.charAt(j-1)==’*’)
  • dp[i][j] = dp[i][k]&&dp[k+1][j]

public boolean checkValidString(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    // Update the * match
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == The '*') {
            dp[i][i] = true; }}// Update dp[i-1][I] match
    for (int i = 1; i < n; i++) {
        dp[i - 1][i] = ((s.charAt(i - 1) = ='(' || s.charAt(i - 1) = =The '*') && (s.charAt(i) == ') ' || s.charAt(i) == The '*'));
    }
    / / update the dp [I] [j]
    for (int i = n - 3; i >= 0; i--) {
        char c1 = s.charAt(i);
        for (int j = i + 2; j < n; j++) {
            char c2 = s.charAt(j);
            if ((c1 == '(' || c1 == The '*') && (c2 == ') ' || c2 == The '*')) {
                dp[i][j] = dp[i + 1][j - 1];
            }
            for (intk = i; k < j && ! dp[i][j]; k++) { dp[i][j] = dp[i][k] && dp[k +1][j]; }}}return dp[0][n-1];
}
Copy the code

• Time complexity O(
  $n^3$)
• Space complexity O(
  $n^2$)

Idea 2: Dynamic planning

• Define dp[I][j] to indicate that j of the first I strings must be completed with parentheses to meet the requirements
• This definition is very important in understanding the transfer equation
• dp[0][0] = true
• Consider the transfer process
• When s.c harAt (I) = ‘(‘, if dp [I] [j] = = true, then the dp [I – 1] [1] = = true, and vice versa (necessary)
• According to the transfer equation, dp[I][j] represents the completion of j closing brackets
• When I == ‘(‘, only j-1 closing parentheses are needed to complete the first i-1 string
• When s.c harAt (I) = ‘) ‘, if dp [I] [j] = = true, then the dp [I – 1] [j + 1) = = true, and vice versa (necessary)
• When s.char (I) = ‘*’, If dp [I] [j] = = true condition is the three scenarios have a meet to the dp [I – 1] [j + 1) = = true | | dp [I – 1] [1] = = true | | dp [I – 1) [j] = = true, and vice versa (necessary)

public boolean checkValidString(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n+1][n+1];
    dp[0] [0] = true;
    for (int i = 1; i <= n; i++) {
        int c1 = s.charAt(i-1);
        for (int j = 0; j <= i; j++) {
            if (c1 == '(') {
                if (j > 0) {
                    dp[i][j] = dp[i - 1][j - 1]; }}else if (c1 == ') ') {
                if (j < i) {
                    dp[i][j] = dp[i - 1][j + 1]; }}else {
                dp[i][j] = dp[i - 1][j];
                if (j > 0) {
                    dp[i][j] |= dp[i - 1][j - 1];
                }
                if (j < i) {
                    dp[i][j] |= dp[i - 1][j + 1]; }}}}return dp[n][0];
}
Copy the code

• Time complexity O(
  $n^2$)
• Space complexity O(
  $n^2$)

Idea 3: double stack simulation

• The first thing that comes to mind for string matching is the stack
• We need two stacks to store *
• Because there is a sequence that can cause string mismatches, the subscript index needs to be stored on the stack
• First check whether all close parentheses can be processed by open parentheses
• If you can’t handle it with the asterisk
• The last remaining open parenthesis and the * stack determine the subscript, and the left parenthesis subscript is less than the * subscript

public boolean checkValidString(String s) {
    Stack<Integer> left = new Stack<>();
    Stack<Integer> star = new Stack<>();
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        if (chars[i] == '('){
            left.push(i);
        }else if (chars[i] == The '*'){
            star.push(i);
        }else{
            if(! left.isEmpty()){ left.pop(); }else if(! star.isEmpty()){ star.pop(); }else{
                return false; }}}// Check whether the left parenthesis can find all symmetric parentheses
    while(! left.isEmpty()&& ! star.isEmpty()){if (left.pop()> star.pop()){
            return false; }}return left.isEmpty();
}
Copy the code

• Time complexity O(
  $n$)
• Space complexity O(
  $n$)

Idea 4: Digital simulation

• That’s a funny way to think about it
• We treat ‘(‘ as score +1, ‘)’ as score -1
• Let’s define the upper and lower bounds of the score interval (L,r)
• L for lowest score, R for highest score
• When an open parenthesis occurs, the upper bound and the next are both ++
• When a closing parenthesis occurs, the upper bound is the same as the next —
• When you have an *, that means it could be open parenthesis or it could be parenthesis, and when you have a close parenthesis the lower bound — when you have an open parenthesis the upper bound ++,
• And l cannot be negative, because if l is negative, it means too many close parentheses, and the asterisk cannot be reduced as a lower bound
• L >r means there are too many close parentheses to satisfy, so you can return false

public boolean checkValidString(String s) {
    int l = 0, r = 0;
    for (char c : s.toCharArray()
    ) {
        if (c == '(') {
            l++;
            r++;
        } else if (c == ') ') {
            l--;
            r--;
        } else {
            l--;
            r++;
        }
        l = Math.max(0, l);
        if (l > r) return false;
    }
    return l == 0;
}
Copy the code

• Time complexity O(
  $n$)
• Space complexity O(
  $1$)

Idea 5: Bidirectional scanning

• We scan the string in both directions
• When scanning from left to right, it is judged that only the right parenthesis represents –, and the rest are ++, which can be interpreted as eliminating the left parenthesis and treating * as the left parenthesis
• When scanning from right to left, it is judged that only the left parenthesis represents –, and the rest are ++, which can be interpreted as eliminating the right parenthesis and treating * as the right parenthesis

public boolean checkValidString(String s) {
    int l = 0, r = 0, n = s.length();
    for (int i = 0; i < n; i++) {
        l += s.charAt(i) == ') ' ? -1 : 1;
        r += s.charAt(n - i - 1) = ='(' ? -1 : 1;
        if (l < 0 || r < 0) {
            return false; }}return true;

}
Copy the code

• Time complexity O(
  $n$)
• Space complexity O(
  $1$)