괄호를 추가하는 다양한 방법 Leetcode 솔루션

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 블룸버그 게시물에서 ByteDance Facebook Flipkart 구글 Microsoft 삼성 Snapchat
동적 프로그래밍 수학 재귀 조회수 37

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

문제 정책

또한 괄호를 추가하는 다양한 방법 LeetCode 솔루션 – "괄호를 추가하는 다양한 방법"에서는 숫자와 연산자의 문자열 표현이 제공된다고 명시되어 있습니다. 숫자와 연산자를 그룹화하기 위해 가능한 모든 방법을 계산하여 가능한 모든 결과를 반환해야 합니다.

임의의 순서로 답을 반환하십시오.

예:

괄호를 추가하는 다양한 방법 Leetcode 솔루션

Input:  expression = "2-1-1"
Output: [0,2]

설명 :

  • ((2-1)-1) = 0, 가능한 결과 중 하나입니다.
  • (2-(1-1)) = 2도 가능한 결과 중 하나입니다.
Input:  expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]

설명 :

  • (2*(3-(4*5))) = -34
  • ((2*3)-(4*5)) = -14
  • ((2*(3-4))*5) = -10
  • (2*((3-4)*5)) = -10
  • (((2*3)-4)*5) = 10
  • 따라서 [-34, -14, -10, -10, 10]이 가능한 결과입니다.

접근

아이디어 :

  1. 이 문제를 해결하기 위한 주요 아이디어는 재귀.
  2. 재귀의 모든 단계에서 작업해야 하는 표현식의 왼쪽 끝과 오른쪽 끝이 있습니다.
  3. 각 인덱스 i에 대해 반복 범위 [l,r] 그리고 다시, [l,i-1] 및 [i+1,r]에 대한 재귀  현재 문자가 연산자이고 각각 ​​이름이 지정된 왼쪽 및 오른쪽 벡터에 반환된 답변 집합을 저장하는 경우.
  4. 이제 왼쪽 벡터와 오른쪽 벡터에서 각각 평가된 표현식에 대해 결과를 적용한 후 모든 새 값을 찾습니다. op b, 여기서 는 왼쪽의 피연산자, b는 오른쪽의 피연산자, op는 연산자입니다.
  5. 현재 상태에 대한 답을 반환합니다. {l,r};
  6. 다음을 사용하여 결과를 메모할 수도 있습니다. 동적 프로그래밍.

암호

괄호를 추가하는 다양한 방법 Leetcode C++ 솔루션:

class Solution {
public:
    map<pair<int,int>,vector<int>> dp;
    vector<int> solve(int l,int r,string expression){
        if(dp.count({l,r})){
            return dp[{l,r}];
        }
        vector<int> ans;
        for(int i=l;i<=r;i++){
            if(expression[i]=='+' or expression[i]=='-' or expression[i]=='*'){
                vector<int> left = solve(l,i-1,expression);
                vector<int> right = solve(i+1,r,expression);
                
                for(auto& num1:left){
                    for(auto& num2:right){
                        if(expression[i]=='+'){
                            ans.push_back(num1+num2);
                        }
                        else if(expression[i]=='-'){
                            ans.push_back(num1-num2);
                        }
                        else{
                            ans.push_back(num1*num2);
                        }
                    }
                }
            }
        }
        if(ans.empty()){
            ans.push_back(stoi(expression.substr(l,r-l+1)));
        }
        return dp[{l,r}] = ans;
    }
    vector<int> diffWaysToCompute(string expression) {
        return solve(0,expression.length()-1,expression);
    }
};

괄호를 추가하는 다양한 방법 Leetcode Java 솔루션:

public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> ret = new LinkedList<Integer>();
        for (int i=0; i<input.length(); i++) {
            if (input.charAt(i) == '-' ||
                input.charAt(i) == '*' ||
                input.charAt(i) == '+' ) {
                String part1 = input.substring(0, i);
                String part2 = input.substring(i+1);
                List<Integer> part1Ret = diffWaysToCompute(part1);
                List<Integer> part2Ret = diffWaysToCompute(part2);
                for (Integer p1 :   part1Ret) {
                    for (Integer p2 :   part2Ret) {
                        int c = 0;
                        switch (input.charAt(i)) {
                            case '+': c = p1+p2;
                                break;
                            case '-': c = p1-p2;
                                break;
                            case '*': c = p1*p2;
                                break;
                        }
                        ret.add(c);
                    }
                }
            }
        }
        if (ret.size() == 0) {
            ret.add(Integer.valueOf(input));
        }
        return ret;
    }
}

괄호를 추가하는 다양한 방법에 대한 복잡성 분석 Leetcode 솔루션

시간 복잡성

위 코드의 시간 복잡성은 카탈루냐 숫자. 모든 상태 [l,r]에 대해 [l,r] 범위에서 반복하고 두 세트 [l,i-1] 및 [i+1,r]로 나눕니다. 이는 카탈루냐 수를 계산하는 것과 반비례합니다. 따라서 시간 복잡도는 카탈루냐 수의 시간 복잡도와 같습니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O(답변 크기). 

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