주어진 문자열의 최대 가중치 변환

난이도 중급
자주 묻는 질문 아마존 BlackRock ByteDance 코드네이션 드 쇼 Expedia JP 모건 올라 택시
동적 프로그래밍 조회수 72

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

문제 정책

주어진 문자열 문제의 최대 가중치 변환은 두 문자 'A'와 'B'로만 구성된 문자열이 주어 졌음을 나타냅니다. 임의의 문자를 토글하여 문자열을 다른 문자열로 변환 할 수있는 작업이 있습니다. 따라서 많은 변형이 가능합니다. 가능한 모든 변환 중에서 최대 가중치 변환의 가중치를 찾으십시오.

암호알고리즘

Weight of string = weight of total pairs + weight of single characters - total number of toggles.
Two different consecutive characters are considered as pairs.
Weight of single pair (both characters are different) = 2
Weight of single character = 1
(These values are just some random values and can be taken as input)

주어진 문자열의 최대 가중치 변환

BA
2

설명 :

문자열 "AA"에는 다음과 같은 네 가지 변환 가능성이 있습니다.

AB → 2 – 1 = 1

학사 → 2 – 1 = 1

AA → 2

비비 → 2

이러한 모든 변환의 무게가 동일하기 때문에 가능한 변환 중 하나를 선택할 수 있습니다.

BAA
3

설명 : 총 8 개의 변환이 있으며 그중 하나의 쌍과 하나의 문자가있는 변환은 최대 값을 갖습니다.

 

주어진 문자열의 최대 가중치 변환 방법

순진한 접근

우리는 각 캐릭터를 토글하여 가능한 모든 변형을 만듭니다. 모든 변환을 수행 한 후 각 변환의 값을 찾은 다음 각 변환의 값을 계산하여 최대 값을 찾습니다.

효율적인 접근

계산을 줄이기 위해 가지 치기를 사용하여 주어진 문자열의 최대 가중치 변환을 찾기 위해 재귀를 사용합니다. 현재 캐릭터와 두 번째 캐릭터가 다르다면 이것은 쌍입니다. 이 경우 첫 번째 문자를 변경하고 앞으로 이동하거나 문자를 전환하지 않고 앞으로 이동하는 두 가지 옵션이 있습니다. 다른 조건은 현재 캐릭터와 두 번째 캐릭터가 동일 할 때입니다. 이 경우 캐릭터를 토글하여 쌍으로 만들거나하지 않고 계속 진행합니다.

초기 (또는 원래) 문제는 더 작은 하위 문제로 변환 될 수 있으므로 동적 프로그래밍 하위 문제를 저장하고 추가로 사용합니다.

암호

주어진 문자열 문제의 최대 가중치 변환을위한 C ++ 코드

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

int pairCost, toggleCost;

int maxWeightOfTransformation(string s, vector<int> &dp, int i, int stringLength){
    //base case
    if(i>=stringLength)
        return 0;
    if(dp[i]!=-1)
        return dp[i];

    // consider current character as a single character(not a pair)
    int answer = 1 + maxWeightOfTransformation(s, dp, i+1, stringLength);
    if(i+1<stringLength){
        if(s[i]!=s[i+1])
            answer = max(pairCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
        else
            answer = max(pairCost-toggleCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
    }
    return dp[i] = answer;
}

int main()
{
    string s;cin>>s;
    cout<<"Enter pairCost and toggleCost"<<endl;
    cin>>pairCost>>toggleCost;
    int stringLength = s.size();
    vector<int> dp(stringLength, -1);
    cout << "Maximum weight of a transformation of "<<s<<" is " <<maxWeightOfTransformation(s, dp, 0, stringLength);
    return 0;
}
AB
Enter pairCost and toggleCost
2 1
Maximum weight of a transformation of AB is 2

주어진 문자열의 최대 가중치 변환을위한 Java 코드

import java.util.*;

class Main{
    static int pairCost, toggleCost;
    
    static int maxWeightOfTransformation(String s, int[] dp, int i, int stringLength){
        //base case
        if(i>=stringLength)
            return 0;
        if(dp[i]!=-1)
            return dp[i];
    
        // consider current character as a single character(not a pair)
        int answer = 1 + maxWeightOfTransformation(s, dp, i+1, stringLength);
        if(i+1<stringLength){
            if(s.charAt(i)!=s.charAt(i+1))
                answer = Math.max(pairCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
            else
                answer = Math.max(pairCost-toggleCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
        }
        return dp[i] = answer;
    }
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        System.out.println("Enter pairCost and toggleCost");
        pairCost=sc.nextInt();
        toggleCost=sc.nextInt();
        int stringLength = s.length();
        int dp[] = new int[stringLength];
        for(int i = 0;i<stringLength;i++)dp[i]=-1;
        int answer = maxWeightOfTransformation(s, dp, 0, stringLength);
        System.out.println("Maximum weight of a transformation of "+s+" is "+answer);
    }
}
AB 
Enter pairCost and toggleCost 
2 1
Maximum weight of a transformation of AB is 2

복잡성 분석

시간 복잡성: 의 위에)

1D DP를 사용하는 알고리즘을 사용했기 때문에 상태 간 전환도 O (1)입니다. 이것은 알고리즘이 O (N) 총 시간 복잡도로 실행되도록합니다.

공간 복잡성: 의 위에)

여기서 우리는 DP에 1D 배열을 사용 했으므로 알고리즘은 O (N) 공간 복잡도를 갖습니다.

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