스택을 사용한 패턴 발생

난이도 중급
라슨 & 투 브로 스택 조회수 73

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

두 개의 배열 pattern [] 및 text []가 주어집니다. 문자 유형. “스택을 사용한 패턴 발생”문제는 스택 데이터 구조를 사용하여 텍스트에서 발견 된 패턴을 제거하면서 텍스트에서 패턴의 총 발생 횟수를 찾는 함수를 생성하도록 요청합니다.

스택을 사용한 패턴 발생

pattern[ ] = {'A','B','C'}

text[ ] = {'A','B','A','B','C','A','B','C','C'}
3

Occurrences found at:
4 7 8

설명 : 위의 이미지에서 세 가지 패턴을 확인할 수 있습니다.

pattern[ ] : {'H','I'}

text[ ] : {'H','I','H','H','I','I','H','I'}
4
Occurrences found at:
1 4 5 7

스택을 사용한 패턴 발생 알고리즘

  1. XNUMX 개 초기화 배열 패턴 [] 및 텍스트 [] 문자 유형.
  2. 두 개의 문자 배열을 매개 변수로 받아들이는 패턴 발생을 찾는 함수를 만듭니다.
  3. 정수 유형의 벡터와 문자열 유형의 스택 데이터 구조를 만듭니다.
  4. 그런 다음 세 개의 정수 변수 p, counter 및 lastOccurrence를 만들고 각각 0,0 및 -10으로 초기화합니다.
  5. 0에서 텍스트 배열 크기로 이동 – 1
  6. 텍스트 배열의 현재 인덱스 값이 패턴 배열의 인덱스 p 값과 같은지 확인합니다. 텍스트 배열의 현재 인덱스 값이 인덱스 크기의 값 – 패턴 배열의 1과 같으면 현재 인덱스를 벡터에 밀어 넣거나 삽입합니다. 카운터를 1 씩 증가시킵니다. lastOccurrence 및 p의 값을 각각 1과 0으로 업데이트합니다. 그렇지 않으면 p를 1 씩 증가시킵니다.
  7. 그렇지 않으면 텍스트 배열의 현재 인덱스 값이 패턴 배열의 첫 번째 인덱스 값과 같은지 확인하고 임시 문자열 변수를 만듭니다. p에서 패턴 배열의 크기로 이동하고 문자열 변수의 현재 인덱스에 문자를 추가합니다. 스택에 임시 문자열 변수를 푸시하고 p 값을 1로 업데이트합니다.
  8. 그렇지 않으면 lastOccurrence가 현재 인덱스와 같은지 확인합니다. 스택이 비어 있으면 p를 1으로 업데이트합니다.
  9. 그렇지 않으면 임시 문자열 변수를 만들고 스택 상단을 팝하고 새로 생성 된 문자열에 저장합니다. string의 첫 문자가 텍스트 배열의 현재 인덱스에있는 값과 같으면 lastOccurence를 현재 인덱스로 업데이트합니다.
  10. 첫 번째 문자의 경우 인덱스 크기의 값과 같습니다. 패턴 배열의 1, 현재 인덱스를 벡터에 푸시하고 카운터를 1 씩 증가시킵니다. 그렇지 않으면 문자열을 스택.
  11. 그렇지 않으면 스택이 비어 있지 않으면 스택을 청소하고 p를 0으로 설정합니다.
  12. 카운터와 벡터 목록을 인쇄합니다.

암호

스택을 사용한 패턴 발생을위한 C ++ 프로그램

#include<bits/stdc++.h> 
using namespace std; 
 
void PatternOccurence(char pattern[], char text[], int ps, int ts){ 
        vector<int> list; 
        stack<string> st; 
        int p = 0; 
        int counter = 0 ; 
        int lastOccurrence = -10; 
        for(int i = 0; i < ts; i ++){ 
            if(text[i] == pattern[p]){ 
                if(text[i] == pattern[ps - 1]){ 
                    list.push_back(i); 
                    counter ++; 
                    lastOccurrence = i; 
                    p = 0; 
                } 
                else{ 
                    p ++; 
                } 
            } 
            else{ 
                if(text[i] == pattern[0]){ 
                    string temp = ""; 
                    for (int i1 = p; i1 < ps; i1 ++){ 
                        temp += pattern[i1]; 
                    }
                    st.push(temp); 
                    p = 1; 
                } 
                else{ 
                    if(lastOccurrence == i - 1){        
                        if(st.empty()){ 
                            p = 0; 
                        }                        
                        else{ 
                            string temp = st.top();
                            st.pop(); 
                
                            if(temp[0] == text[i]){ 
                                lastOccurrence = i; 
                
                                if(temp[0] == pattern[ps - 1]){ 
                                    list.push_back(i); 
                                    counter ++; 
                                }                                 
                                else{ 
                                    temp = temp.substr(1, temp.length()); 
                                    st.push(temp); 
                                } 
                            } 
                            else{ 
                                if(!st.empty()) 
                                    while(!st.empty()){
                                        st.pop();
                                    } 
                                    p = 0; 
                                } 
                            } 
                        } 
                        
                    else{ 
                        if (!st.empty()){ 
                            while(!st.empty()){
                                st.pop();
                            }  
                        }
                        p = 0; 
                    } 
                } 
            } 
        } 
        cout<<counter<<endl;
        if(counter>0){
            cout<<"Occurrences found at:"<<endl;
            for(auto i = list.begin(); i != list.end(); ++i){ 
                cout << *i << " "; 
            }
        }
    }   
int main(){ 
    char pattern[] = {'A','B','C'}; 
    char text[] = {'A','B','A','B','C','A','B','C','C'}; 
    int ps = sizeof(pattern)/sizeof(pattern[0]);
    int ts = sizeof(text)/sizeof(text[0]);
    PatternOccurence(pattern, text, ps, ts);
    return 0; 
}
3
Occurrences found at:
4 7 8

스택을 사용한 패턴 발생을위한 Java 프로그램

import java.util.ArrayList; 
import java.util.Stack; 

class StackImplementation{ 

    class Data{ 
        ArrayList<Integer> present; 
        int count; 
        
        public Data(ArrayList<Integer> present, int count){ 
            this.present = present; 
            this.count = count; 
        } 
    } 
    
    public Data Solution(char pattern[], char text[]){ 
        ArrayList<Integer> list = new ArrayList<>(); 
        Stack<String>  stack = new Stack<>(); 
        
        int p = 0; 
        int counter = 0 ; 
        int lastOccurrence = -10; 
        
        for(int i = 0; i < text.length; i ++){ 
            if(text[i] == pattern[p]){ 
            
                if(text[i] == pattern[pattern.length - 1]){ 
                    list.add(i); 
            
                    counter ++; 
                    lastOccurrence = i; 
                    p = 0; 
                } 
                
                else{ 
                    p ++; 
                } 
            } 
        
            else{ 
                if(text[i] == pattern[0]){ 
                    String temp = ""; 
                    
                    for (int i1 = p; i1 < pattern.length; i1 ++){ 
                        temp += pattern[i1]; 
                    }
        
                    stack.push(temp); 
                    p = 1; 
                } 
                
                else{ 
                    if(lastOccurrence == i - 1){ 
        
                        if(stack.isEmpty()){ 
                            p = 0; 
                        }
                        
                        else{ 
                            String temp = stack.pop(); 
                
                            if (temp.charAt(0) == text[i]){ 
                                lastOccurrence = i; 
                
                                if(temp.charAt(0) == pattern[pattern.length - 1]){ 
                                    list.add(i); 
                                    counter ++; 
                                } 
                                
                                else{ 
                                    temp = temp.substring(1, temp.length()); 
                                    stack.push(temp); 
                                } 
                            } 
        
                            else{ 
                                if (!stack.isEmpty()) 
                                    stack.clear(); 
                                    p = 0; 
                                } 
                            } 
                        } 
                        
                    else{ 
                        if (!stack.isEmpty()){ 
                            stack.clear(); 
                        }
                        p = 0; 
                    } 
                } 
            } 
        } 
        return new Data(list, counter); 
    } 
    
    public static void main(String args[]){ 
        char[] pattern = "ABC".toCharArray(); 
        
        char[] text = "ABABCABCC".toCharArray(); 
        
        StackImplementation obj = new StackImplementation(); 
        Data data = obj.Solution(pattern, text); 
        
        int count = data.count; 
        ArrayList<Integer> list = data.present; 
        System.out.println(count); 
        
        if(count > 0){ 
            System.out.println("Occurrences found at:"); 
            
            for(int i : list){ 
                System.out.print(i + " ");
            }
        } 
    } 
}
3
Occurrences found at:
4 7 8

복잡성 분석

시간 복잡성

O (ts) 여기서 ts는 문자 배열 text []의 문자 수입니다.

공간 복잡성

O (ts) 문자를 저장하기 위해 공백을 사용했기 때문입니다.

균열 시스템 설계 인터뷰
Translate »