Μέγιστος μετασχηματισμός βάρους μιας δεδομένης συμβολοσειράς


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις αμαζόνα BlackRock ByteDance CodeNation DE Shaw Expedia JP Morgan Ola Cabs
Δυναμικός προγραμματισμός κορδόνι

Δήλωση προβλήματος

Ο μέγιστος μετασχηματισμός βάρους ενός δεδομένου προβλήματος συμβολοσειράς δηλώνει ότι σε μια συμβολοσειρά που αποτελείται μόνο από δύο χαρακτήρες «Α» και «Β». Έχουμε μια λειτουργία όπου μπορούμε να μετατρέψουμε τη συμβολοσειρά σε άλλη συμβολοσειρά με εναλλαγή οποιουδήποτε χαρακτήρα. Έτσι είναι δυνατοί πολλοί μετασχηματισμοί. Από όλους τους πιθανούς μετασχηματισμούς, μάθετε το βάρος του μέγιστου βάρους μετασχηματισμού.

Αλγόριθμος

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

BA → 2 - 1 = 1

AA → 2

BB → 2

Δεδομένου ότι όλοι αυτοί οι μετασχηματισμοί ζυγίζουν το ίδιο, μπορούμε να επιλέξουμε έναν από τους πιθανούς μετασχηματισμούς.

BAA
3

Επεξήγηση: Υπάρχουν συνολικά 8 μετασχηματισμοί, από τους οποίους οι μετασχηματισμοί που έχουν ένα ζεύγος και έναν μεμονωμένο χαρακτήρα έχουν τη μέγιστη τιμή.

 

Προσέγγιση για μέγιστο μετασχηματισμό βάρους μιας δεδομένης συμβολοσειράς

Naive προσέγγιση

Κάνουμε όλους τους δυνατούς μετασχηματισμούς με εναλλαγή κάθε χαρακτήρα. Αφού πραγματοποιήσουμε όλους τους μετασχηματισμούς, βρίσκουμε την τιμή κάθε μετασχηματισμού και μετά βρίσκουμε τη μέγιστη τιμή υπολογίζοντας την τιμή κάθε μετασχηματισμού.

Αποτελεσματική προσέγγιση

Θα χρησιμοποιήσουμε την αναδρομή για να βρούμε τον μέγιστο μετασχηματισμό βάρους μιας δεδομένης συμβολοσειράς, χρησιμοποιώντας το κλάδεμα για να μειώσουμε τους υπολογισμούς. Εάν έχουμε τον τρέχοντα χαρακτήρα και τον δεύτερο χαρακτήρα διαφορετικό, αυτό είναι ένα ζευγάρι. Σε αυτήν την περίπτωση, έχουμε δύο επιλογές είτε να αλλάξουμε τον πρώτο χαρακτήρα και να προχωρήσουμε είτε να μην αλλάξουμε τους χαρακτήρες και να προχωρήσουμε μπροστά. Η άλλη συνθήκη θα ήταν όταν έχουμε τον τρέχοντα χαρακτήρα και τους δεύτερους χαρακτήρες ίδιο. Σε αυτήν την περίπτωση, θα αλλάξουμε τον χαρακτήρα και θα τον κάνουμε ζευγάρι, ή δεν το κάνουμε και θα προχωρήσουμε μπροστά.

Δεδομένου ότι το αρχικό (ή το αρχικό) πρόβλημα μπορεί να μετατραπεί σε μικρότερα υποπροβλήματα, θα το χρησιμοποιήσουμε δυναμικό προγραμματισμό για να αποθηκεύσετε τα υποπροβλήματα και να τα χρησιμοποιήσετε περαιτέρω.

Κώδικας

Κωδικός 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 Code για μέγιστο μετασχηματισμό βάρους μιας δεδομένης συμβολοσειράς

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) συνολική πολυπλοκότητα χρόνου.

Διαστημική πολυπλοκότητα: ΕΠΙ)

Εδώ έχουμε χρησιμοποιήσει έναν πίνακα 1D για DP, επομένως ο αλγόριθμος έχει πολυπλοκότητα χώρου O (N).