Solving "riduzione stringa" sfida

Question

ho visto varie discussioni e tentativi di codice a risolvere il problema "String reduction" da interviewstreet.com, ma nessuno di loro lo fa tramite la programmazione dinamica.

Pubblicata nella sezione Dynamic Programming, il problema è descritto come segue:

Data una stringa costituita da una, bec di, possiamo eseguire la seguente operazione: prendere qualsiasi due caratteri distinte adiacenti e sostituirla con il terzo personaggio. Ad esempio, se 'a' e 'c' sono adiacenti, possono essere sostituiti con 'b'.

Qual è la stringa più piccola che può risultare applicando questa operazione ripetutamente?

Il problema può essere risolto utilizzando esaustivo di ricerca a forza bruta, creando di fatto un albero di tutte le possibili sostituzioni:

// this is more or less pseudo code from my head 
int GetMinLength(string s) 
{ 
    // solve edge cases 
    if (s.Length == 1) return 1; 
    if (s.Length == 2) return ReduceIfPossible(s); 

    // recursive brute force 
    int min = s.Length; 
    for (int i = 0; i<s.Length-1; i++) 
    { 
     if (s[i] != s[i+1]) 
     { 
      var next = GetMinLength(
        s.Substring(0, i) + 
        Reduce(s[i], s[i + 1]) + 
        s.Substring(i + 2) 
       ); 

      if (next < min) min = next; 
     } 
    } 
} 

questo non riesce, ovviamente, per i più grandi N (N <= 100), quindi sto cercando di rompere in sottoproblemi più piccoli, memorizzali e unisci i risultati.

Il problema è che non riesco a determinare lo stato che avrebbe "optimal substructure", necessario per applicare la programmazione dinamica (o in altre parole per "unire" i risultati dei sotto-problemi). Ridurre al minimo una parte della stringa non garantisce che la stringa finale sarà davvero la soluzione più piccola.

Quale sarebbe il sottoproblema "stato" in questo caso, che potrebbe essere fusa verso la soluzione finale?

Answer 1

Ciò che rende questo difficile è che è necessario trattare questo come 2 problemi di programmazione dinamici di fila.

1. Compilare un tavolo di, per carattere si finisce con, per posizione iniziale, tutte le possibili posizioni finali che sono un blocco che può essere ridotto a quel personaggio.
2. La lunghezza più piccola a cui è possibile ridurre i caratteri finali i della stringa. (La tabella creata nel passaggio 1 può essere utilizzata per ridurre ricorsivamente questo problema ai sottoproblemi già risolti.)

Il secondo fornisce la risposta. È molto più semplice se hai già risolto il primo.

Answer 2

Si inizia creando una struttura che descrive una teoria della soluzione. Include il numero di caratteri considerati e la stringa codificata fino ad ora, e il caso peggiore e il caso migliore per la teoria.

All'inizio c'è solo una teoria - nessun carattere trasformati. Il caso migliore è una stringa di lunghezza 1 (ad esempio, si applica sempre una regola e la stringa può essere ridotta a un carattere e il caso peggiore è N, dove non si applicano regole).

encoded string = ""; 
encoded index = 0; 
worst case = N; 
best case = 1; 

Ora inizia l'incremento dell'indice di uno e l'aggiunta di un carattere alla stringa codificata. Se non si applicano regole, mantieni intatta questa teoria. Se si applica una regola, devi prendere una decisione: applicare la regola o non farlo. Quindi quando aggiungi un personaggio duplichi la teoria per ogni regola che potrebbe applicarsi all'ultimo carattere e mantieni una versione per nessuna regola applicata. E aggiorni il caso migliore e il caso peggiore per ogni teoria.

All'inizio il numero di teorie si moltiplica molto rapidamente. Ma alla fine si arriva a una situazione in cui il caso peggiore per alcune teorie è migliore del caso migliore per altre teorie.

Quindi, ogni volta che si fa avanzare l'indice, si eliminano le teorie in cui il caso migliore è peggiore rispetto alla teoria con il peggiore dei casi. Man mano che l'indice si avvicina a N, la maggior parte delle teorie verrà abbandonata. codice

Answer 3

Spoiler Alert:

public static int findMinReduction(String line){ 
    //Pseudocode: 
    //Count the number of occurences of each letter in the input string. 
    //If two of these counts are 0, then return string.length 
    //Else if (all counts are even) or (all counts are odd), then return 2 
    //Else, then return 1 

    int len = line.length(); 
    String a_reduce = line.replaceAll("c", "").replaceAll("b", ""); 
    String b_reduce = line.replaceAll("a", "").replaceAll("c", ""); 
    String c_reduce = line.replaceAll("a", "").replaceAll("b", ""); 

    int a_occurances = a_reduce.length(); 
    int b_occurances = b_reduce.length(); 
    int c_occurances = c_reduce.length(); 

    if ((a_occurances == b_occurances && a_occurances == 0) || 
     (a_occurances == c_occurances && a_occurances == 0) || 
     (b_occurances == c_occurances && b_occurances == 0)){ 
     return len; 
    } 
    else{ 
     if (a_occurances % 2 == 0 && 
      b_occurances % 2 == 0 && 
      c_occurances % 2 == 0){ 
      return 2; 
     } 
     if (a_occurances % 2 != 0 
      && b_occurances % 2 != 0 && 
      c_occurances % 2 != 0){ 
      return 2; 
     } 
    } 
    return 1; 
} 

Complessità:

Questo è un O (n) tempo complessità, all'aumentare della dimensione di ingresso, la quantità di lavoro da fare è lineare con la dimensione dell'input. Il che è rapidissimo, possiamo elaborare stringhe di dimensioni megabyte e elaborarle ancora in frazioni di secondo.

Algoritmo trovato qui con l'analisi completa del perché questo algoritmo funziona:

stumped on a Java interview, need some hints