문자열에서 중첩 된 괄호의 최대 깊이 찾기


난이도 중급
자주 묻는 질문 아마존 페이스북 서비스
스택

주어진 문자열 s. 주어진 안에 중첩 된 괄호의 최대 깊이를 인쇄하는 코드를 작성하십시오. .

문자열에서 중첩 된 괄호의 최대 깊이 찾기

입력 : s =“(a (b) (c) (d (e (f) g) h) I (j (k) l) m)”

출력 : 4

입력 : s =“(p ((q)) ((s) t))”

출력 : 3

스택 사용

암호알고리즘

  1. 길이가 n 인 문자열 s를 초기화합니다.
  2. 만들기 스택 괄호와 두 개의 변수를 저장하여 최대 값과 현재 최대 값을 저장하고 값을 0으로 설정합니다.
  3. 문자열을 가로 질러 현재 문자가 여는 괄호인지 확인하고 스택에 밀어 넣고 현재 최대 값을 증가시킵니다. 현재 최대 값이 최대 값보다 큰 경우 최대 값을 현재 최대 값으로 업데이트합니다.
  4. 그렇지 않으면 현재 문자가 닫는 괄호이면 스택의 맨 위 문자를 팝합니다. 현재 최대 값이 0보다 크고 팝된 문자가 여는 괄호인지 확인하고 현재 최대 값을 줄이면 -1을 반환합니다.
  5. 스택이 비어 있지 않으면 -1을 반환합니다.
  6. Else는 최대 값을 반환합니다.

문자열에서 중첩 된 괄호의 최대 깊이를 찾는 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 

class Stack{  
    public: 
        int top;  
        unsigned capacity;  
        char* array;  
};  
  
Stack* createStack(unsigned capacity){  
    Stack* stack = new Stack(); 
    stack->capacity = capacity;  
    stack->top = -1;  
    stack->array = new char[(stack->capacity * sizeof(char))];  
    return stack;  
}  
  
int isFull(Stack* stack){ 
    return stack->top == stack->capacity - 1; 
}  
  
int isEmpty(Stack* stack){ 
    return stack->top == -1;
}  
  
void push(Stack* stack, char item){  
    if(isFull(stack))  
        return;  
    stack->array[++stack->top] = item;  
}  
  
char pop(Stack* stack){  
    if(isEmpty(stack))  
        return -1;  
    return stack->array[stack->top--];  
}  

int maxDepth(string s){ 
    int n = s.length();  
    Stack* stack = createStack(n);
    int current_max = 0; 
    int max = 0;   
  
    for(int i = 0; i<n; i++){
        
        if(s[i] == '('){ 
            push(stack, s[i]);
            current_max++; 
  
            if(current_max > max){ 
                max = current_max;
            }    
        } 
        
        else if(s[i] == ')'){ 
            char c = pop(stack);
            if((current_max > 0) && (c == '(')){ 
                current_max--; 
            }    
            else{
                return -1;
            }    
        } 
    } 
  
    if(!isEmpty(stack)){ 
        return -1; 
    }    
  
    return max; 
} 
  
int main(){
    
    string s = "( a(b) (c) (d(e(f)g)h) I (j(k)l)m)"; 
    cout<<maxDepth(s); 
    
    return 0; 
}
4

문자열에서 중첩 된 괄호의 최대 깊이를 찾는 Java 프로그램

import java.util.*; 
  
class Stack{ 
    int size; 
    int top; 
    char[] a;  
  
    boolean isEmpty(){ 
        return(top < 0); 
    } 
      
    Stack(int n){ 
        top = -1; 
        size = n; 
        a = new char[size]; 
    } 
  
    boolean push(char x){ 
        if (top >= size){ 
            System.out.println("Stack Overflow"); 
            return false; 
        } 
        else{ 
            a[++top] = x; 
            return true; 
        } 
    } 
  
    char pop(){ 
        if(top < 0){ 
            System.out.println("Stack Underflow"); 
            return 0; 
        } 
        else{ 
            char x = a[top--]; 
            return x; 
        } 
    } 
}

class Depth{
    
    static int maxDepth(String s){
        
        int current_max = 0;
        int max = 0; 
        int n = s.length(); 
        Stack stack = new Stack(n);
  
        for(int i = 0; i < n; i++){ 
            if(s.charAt(i) == '('){ 
                current_max++; 
                stack.push(s.charAt(i));
  
                if(current_max > max){ 
                    max = current_max; 
                } 
            } 
            else if(s.charAt(i) == ')'){ 
                
                char c = stack.pop();
                
                if((current_max > 0) && (c == '(')){ 
                    current_max--; 
                } 
                else{ 
                    return -1; 
                } 
            } 
        } 
  
        if(!stack.isEmpty()){ 
            return -1; 
        } 
  
        return max; 
    } 
  
    public static void main(String[] args){
        
        String s = "( a(b) (c) (d(e(f)g)h) I (j(k)l)m)"; 
        System.out.println(maxDepth(s)); 
        
    } 
}
4

복잡성 분석

시간 복잡성 : O (n) 여기서 n은 문자열의 크기입니다.

보조 공간 : O (n) n 문자를 저장하기 위해 스택의 공간을 사용했기 때문입니다.

스택을 사용하지 않고

암호알고리즘

  1. 길이가 n 인 문자열 s를 초기화합니다.
  2. 최대 값과 현재 최대 값을 저장할 두 개의 변수를 만들고 값을 0으로 설정합니다.
  3. 문자열을 탐색하고 현재 문자가 여는 괄호인지 확인하고 현재 최대 값을 증가시킵니다. 현재 최대 값이 최대 값보다 큰 경우 최대 값을 현재 최대 값으로 업데이트합니다.
  4. 그렇지 않으면 현재 문자가 닫는 괄호이면 현재 최대 값이 0보다 크면 감소하고 그렇지 않으면 -1을 반환합니다.
  5. 현재 최대 값이 0이 아니면 -1을 반환합니다.
  6. Else는 최대 값을 반환합니다.

문자열에서 중첩 된 괄호의 최대 깊이를 찾는 C ++ 프로그램

#include <iostream> 
using namespace std; 
  
int maxDepth(string s){ 
    int current_max = 0; 
    int max = 0;   
    int n = s.length(); 
  
    for(int i = 0; i<n; i++){ 
        if(s[i] == '('){ 
            current_max++; 
  
            if(current_max > max){ 
                max = current_max;
            }    
        } 
        else if(s[i] == ')'){ 
            if(current_max > 0){ 
                current_max--; 
            }    
            else{
                return -1;
            }    
        } 
    } 
  
    if(current_max != 0){ 
        return -1; 
    }    
  
    return max; 
} 
  
int main(){
    
    string s = "( a(b) (c) (d(e(f)g)h) I (j(k)l)m)"; 
    cout<<maxDepth(s); 
    
    return 0; 
}
4

문자열에서 중첩 된 괄호의 최대 깊이를 찾는 Java 프로그램

class Depth{
    
    static int maxDParenthesis(String s){
    
        int currentmax = 0;
        int max = 0; 
        int n = s.length(); 
  
        for(int i = 0; i < n; i++){ 
            if(s.charAt(i) == '('){ 
                currentmax++; 
  
                if(currentmax > max){ 
                    max = currentmax; 
                } 
            } 
            else if(s.charAt(i) == ')'){ 
                if(currentmax > 0){ 
                    currentmax--; 
                } 
                else{ 
                    return -1; 
                } 
            } 
        } 
    
        if(currentmax != 0){ 
            return -1; 
        } 
        
        return max; 
    } 
    
    public static void main(String[] args){
    
        String s = "( a(b) (c) (d(e(f)g)h) I (j(k)l)m)";
        
        System.out.println( maxDParenthesis(s) ); 
    
    } 
}
4

복잡성 분석

시간 복잡성 : O (n) 여기서 n은 문자열의 크기입니다.

보조 공간 : O (1) 우리는 일정한 추가 공간을 사용했기 때문입니다.

참조