문자열을 훌륭한 Leetcode 솔루션으로 만들기 TutorialCup

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

Twitter Facebook 링크드인 버퍼 레딧 텀블러

차례

문제 정책

“Make The String Great”문제에서 문자열은 소문자와 대문자로 구성됩니다. 우리는 문자열을 나쁘게 만드는 문자열에서 인접한 문자를 제거하여이 문자열을 좋게 만들어야합니다.
좋은 문자열은 두 문자가 동일하지만 대소 문자가 다른 두 개의 인접한 문자가없는 문자열입니다. 문자열을 좋게 만들기 위해이 작업을 여러 번 수행 할 수 있습니다.

예

s = "leEeetcode"

"leetcode"

설명 :

첫 번째 단계에서 인덱스 1과 2 또는 2와 3을 선택할 수 있습니다. 둘 다 "leEeetcode"를 "leetcode"로 줄입니다.

"abBAcC"

""

설명 :

가능한 시나리오는 다음과 같습니다.
문자열 훌륭한 Leetcode 솔루션 만들기

접근

주어진 문자열에는 동일하지만 대소 문자가 반대 인 인접 문자가 있습니다. 따라서 우리가해야 할 일은이 두 문자를 만날 때마다 둘 다 제거하고 나머지 문자열에 대해 프로세스를 다시 반복해야하는 것입니다.

이를 위해 우리가 할 수있는 것은 주어진 문자열의 첫 번째 문자부터 반복하고 나쁘지 않을 때까지 결과 문자열에 문자를 추가 할 수 있다는 것입니다.
현재 문자를 추가하기 전에이 문자를 res 문자열에 추가하면 res 문자열의 마지막 문자와 비교하여이 문자를 잘못 만들지 여부를 확인합니다. 적분 차이 (아스키)이 두 문자 사이는 32와 같으면 나쁜 조합입니다. 그렇지 않으면 좋습니다. 이를 바탕으로 다음 작업을 수행합니다.

캐릭터를 추가해도 나쁘지 않으면 해당 캐릭터를 res에 추가하기 만하면됩니다.
그렇지 않으면 res 문자열의 마지막 문자를 추가하지 않고 제거합니다.

위의 알고리즘을 위해 우리는 스택 문자를 끝까지 밀고 끝에서 문자를 튀어 나오는 데이터 구조.
C ++에서는 다음을 사용할 수도 있습니다. 문자열 클래스 문자 스택으로 스택 클래스와 같은 push_back () 및 pop_back () 작업을 사용할 수 있습니다.

실시

문자열 훌륭한 Leetcode 솔루션을 만들기위한 C ++ 프로그램

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

string makeGood(string s) {

    string goodString;

    for(char ch:s)
    {
        if((!goodString.empty()) && abs(goodString.back()-ch)==32)  
            goodString.pop_back();
        else  
            goodString.push_back(ch);
    }

    return goodString;
}

int main() 
{
    string s = "leEeetcode";
    
    cout<<makeGood(s)<<endl;

  return 0; 
}

"leetcode"

문자열 훌륭한 Leetcode 솔루션을 만들기위한 Java 프로그램

import java.lang.*;
import java.util.*;

class Rextester
{  
    public static String makeGood(String s) {

        Stack<Character> stack= new Stack<Character>();

        for(int i=0;i<s.length();i++)
        {
            if((!stack.isEmpty()) && Math.abs(stack.peek()-s.charAt(i))==32 )
                stack.pop();
            else
                stack.push(s.charAt(i));
        }

        char res[]= new char[stack.size()];
        
        for(int i=res.length-1;i>=0;i--) 
            res[i]= stack.pop();

        return new String(res);

    }
    
    public static void main(String args[])
    {
        String s = "leEeetcode";

        System.out.println(makeGood(s));
        
    }
}

"leetcode"

문자열을 훌륭한 Leetcode 솔루션으로 만들기위한 복잡성 분석

시간 복잡성

의 위에) : 여기서 n은 입력 문자열의 길이입니다. 우리는 단일 루프에서 문자열을 반복하기 때문입니다. 따라서 시간 복잡도는 n 차가됩니다.

공간 복잡성

의 위에) : 최종 결과를 저장하기 위해 스택을 사용하고 있습니다. 따라서 사용되는 공간은 n 차, 즉 O (n)입니다.

Twitter Facebook 링크드인 버퍼 레딧 텀블러