Ricerca di una stringa minima che soddisfa alcune condizioni

Question

Recentemente, mi è stato chiesto il seguente problema durante un'intervista.

Data una stringa S, ho bisogno di trovare un'altra stringa S2 tale che S2 sia una sottosequenza di S e anche S è una sottosequenza di S2 + retromarcia (S2). Qui '+' significa concatenazione. Ho bisogno di produrre la minima lunghezza possibile di S2 per data S.

Mi è stato detto che questo è un problema di programmazione dinamica, ma non sono riuscito a risolverlo. Qualcuno può aiutarmi con questo problema?

EDIT-

C'è un modo per fare questo in O (N 2 ) o meno.

Answer 1

Ogni carattere da S può essere incluso in S2 o no. Con questo possiamo costruire la ricorsione che cerca due casi:

• primo carattere di S viene utilizzato per la copertura,
• primo carattere di S non è utilizzato per la copertura,

e calcolare minimo di queste due copertine. Per implementarlo, è sufficiente tenere traccia di quanto S è coperto con S2 + reverse (S2) già scelto.

Ci sono ottimizzazioni in cui sappiamo quale sia il risultato (copertura trovata, non può avere copertura) e non è necessario prendere il primo carattere per la copertina se non coprirà qualcosa.

implementazione di Python Semplice:

cache = {} 

def S2(S, to_cover): 
    if not to_cover: # Covered 
     return '' 
    if not S:   # Not covered 
     return None 
    if len(to_cover) > 2*len(S): # Can't cover 
     return None 
    key = (S, to_cover) 
    if key not in cache: 
     without_char = S2(S[1:], to_cover)  # Calculate with first character skipped 
     cache[key] = without_char 
     _f = to_cover[0] == S[0] 
     _l = to_cover[-1] == S[0] 
     if _f or _l: 
      # Calculate with first character used 
      with_char = S2(S[1:], to_cover[int(_f):len(to_cover)-int(_l)]) 
      if with_char is not None: 
       with_char = S[0] + with_char # Append char to result 
       if without_char is None or len(with_char) <= len(without_char): 
        cache[key] = with_char 
    return cache[key] 

s = '21211233123123213213131212122111312113221122132121221212321212112121321212121132' 
c = S2(s, s) 
print len(s), s 
print len(c), c 

Answer 2

Diciamo che S2 è "mela". Poi possiamo fare questo presupposto:

S2 + reverseS2> = S> = S2
"appleelppa"> = S> = "mela"

Così la S data darà qualcosa includendo "apple" a non più di "appleelppe". Potrebbe essere "appleel" o "appleelpp".

String S ="locomotiffitomoc"; 
// as you see S2 string is "locomotif" but 
// we don't know S2 yet, so it's blank 
String S2 = ""; 
for (int a=0; a<S.length(); a++) { 
    try { 
     int b = 0; 
     while (S.charAt(a - b) == S.charAt(a + b + 1)) 
      b++; 
     // if this for loop breaks that means that there is a character that doesn't match the rule 
     // if for loop doesn't break but throws an exception we found it. 
    } catch (Exception e) { 
     // if StringOutOfBoundsException is thrown this means end of the string. 
     // you can check this manually of course. 
     S2 = S.substring(0,a+1); 
     break; 
    } 
} 
System.out.println(S2); // will print out "locomotif" 

Complimenti, hai trovato il minimo S2.

Answer 3

Ci sono 2 aspetti importanti in questo problema.

1. Poiché occorre S come una stringa di S2 + retromarcia (S2), S2 dovrebbe avere atleast n/2 lunghezza.
2. Dopo concatenazione di S2 e retromarcia (S2), c'è un modello in cui alfabeti ripete come

Quindi la soluzione è di controllare dal centro di S a fine S per ogni elemento consecutivo.Se ne trovi uno, controlla gli elementi su entrambi i lati come mostrato.

Ora, se si è in grado di raggiungere fino alla fine della stringa, quindi il numero minimo di elementi (risultato) è la distanza dall'inizio al punto in cui si trova elementi consecutivi. In questo esempio C i.e 3.

Sappiamo che questo potrebbe non succedere sempre. potreste non essere in grado di trovare elementi consecutivi al centro. Diciamo che gli elementi consecutivi sono dopo il centro, quindi possiamo fare lo stesso test.

stringa principale

Substring

stringa concatenata

Ora arriva t lui maggiore dubbio. Perché consideriamo solo la parte sinistra a partire dal centro? La risposta è semplice, la stringa concatenata è fatta da S + reverse (S). Quindi siamo sicuri che l'ultimo elemento nella sottostringa arriva consecutivamente nella stringa concatenata. Non c'è modo che nessuna ripetizione nella prima metà della stringa principale possa dare un risultato migliore perché almeno dovremmo avere gli alfabeti n nella stringa finale concatenata

Ora la questione della complessità: La ricerca di alfabeti consecutivi dà un massimo di O (n) Ora il controllo degli elementi su entrambi i lati in modo iterativo può fornire la peggiore complessità di O (n). I massimo n/2 confronti. Potremmo fallire molte volte facendo il secondo controllo in modo da avere una relazione moltiplicativa tra le complessità i.e O (n * n).

Credo che questa sia una soluzione corretta e non ha trovato ancora alcuna scappatoia.